/*
 * Copyright (c) [2022] Huawei Technologies Co.,Ltd.All rights reserved.
 *
 * OpenArkCompiler is licensed under Mulan PSL v2.
 * You can use this software according to the terms and conditions of the Mulan PSL v2.
 * You may obtain a copy of Mulan PSL v2 at:
 *
 *     http://license.coscl.org.cn/MulanPSL2
 *
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT, MERCHANTABILITY OR
 * FIT FOR A PARTICULAR PURPOSE.
 * See the Mulan PSL v2 for more details.
 */
#include "me_gvn.h"
#include <algorithm>
#include <cstddef>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <memory>
#include <unordered_map>
#include <utility>
#include <variant>
#include <vector>
#include "bb.h"
#include "cfg_primitive_types.h"
#include "dominance.h"
#include "global_tables.h"
#include "irmap.h"
#include "maple_phase.h"
#include "me_cfg.h"
#include "me_dominance.h"
#include "me_function.h"
#include "me_ir.h"
#include "me_irmap.h"
#include "me_option.h"
#include "me_phase_manager.h"
#include "meexpr_use_info.h"
#include "mempool.h"
#include "mempool_allocator.h"
#include "mir_const.h"
#include "mir_nodes.h"
#include "mir_type.h"
#include "mpl_logging.h"
#include "mpl_number.h"
#include "opcode_info.h"
#include "opcodes.h"
#include "scc.h"
#include "types_def.h"
#include "me_lower_globals.h"

namespace maple {
namespace {
size_t kVnNum = 0;
size_t kRankNum = 0;
size_t kVnExprNum = 1;
constexpr size_t kInvalidVnExprNum = 0;
constexpr uint8 kMaxTreeSize = 20;

bool kDebug = false;

#define DEBUG_LOG() \
  if (kDebug) LogInfo::MapleLogger() << "[GVN] "

constexpr size_t kPrefixAlign = 6; // size of "[GVN] "

void InitNum() {
  kVnNum = 0;
  kRankNum = 0;
  kVnExprNum = 1;
}

const ScalarMeExpr &GetRealMu(const ScalarMeExpr &expr, std::set<const MePhiNode *> &visited) {
  if (!expr.IsDefByPhi()) {
    return expr;
  }
  auto &defPhi = expr.GetDefPhi();
  if (visited.count(&defPhi) != 0) {
    return expr;
  }
  visited.emplace(&defPhi);
  const ScalarMeExpr *firstReal = nullptr;
  for (auto *opnd : defPhi.GetOpnds()) {
    auto &realOpnd = GetRealMu(*opnd, visited);
    firstReal = firstReal ? firstReal : &realOpnd;
    if (&realOpnd != firstReal) {
      return expr;
    }
  }
  return *firstReal;
}

std::unique_ptr<MeExpr> CloneMeExpr(const MeExpr &expr, MapleAllocator *ma) {
  switch (expr.GetMeOp()) {
    case kMeOpIvar: {
      return std::make_unique<IvarMeExpr>(ma, kInvalidExprID, static_cast<const IvarMeExpr &>(expr));
    }
    case kMeOpOp: {
      return std::make_unique<OpMeExpr>(static_cast<const OpMeExpr &>(expr), kInvalidExprID);
    }
    case kMeOpNary: {
      return std::make_unique<NaryMeExpr>(ma, kInvalidExprID, static_cast<const NaryMeExpr &>(expr));
    }
    case kMeOpConst:
    case kMeOpVar:
    case kMeOpReg:
    case kMeOpAddrof:
    case kMeOpAddroffunc:
    case kMeOpAddroflabel:
    case kMeOpConststr:
    case kMeOpConststr16:
    case kMeOpSizeoftype:
    case kMeOpFieldsDist:
    case kMeOpGcmalloc: {
      return nullptr;
    }
    default:
      ASSERT(false, "Unknow meop, NYI!");
      return nullptr;
  }
}

// when a reachable BB in scc is first time visited, touch all stmts(phis) in it
bool NeedTouchBB(const BB &bb, const std::set<const BB *> &visited, const std::set<const BB *> &bbInScc) {
  return visited.count(&bb) == 0 && bbInScc.count(&bb) != 0;
}
}

// == Start of Vn
class CongruenceClass {
 public:
  struct MeExprCmp {
    bool operator()(const MeExpr *e1, const MeExpr *e2) const {
      return e1->GetExprID() < e2->GetExprID();
    }
  };

  explicit CongruenceClass(MapleAllocator &alloc)
      : id(kVnNum++), exprList(alloc.Adapter()), leaderList(alloc.Adapter()) {}

  CongruenceClass(MeExpr &expr, MapleAllocator &alloc)
      : id(kVnNum++), exprList(alloc.Adapter()), leaderList(alloc.Adapter()) {
    exprList.insert(&expr);
  }

  MeExpr *GetRepExpr() const {
    return exprList.empty() ? nullptr : *exprList.begin();
  }

  void AddExpr(MeExpr &expr) {
    DEBUG_LOG() << "Add expr <mx" << expr.GetExprID() << "> to <vn" << this->GetID() << ">\n";
    exprList.insert(&expr);
    if (kDebug) { this->Dump(kPrefixAlign); }
  }

  void RemoveExpr(MeExpr &expr) {
    DEBUG_LOG() << "Remove expr <mx" << expr.GetExprID() << "> from <vn" << this->GetID() << ">\n";
    exprList.erase(&expr);
    if (kDebug) { this->Dump(kPrefixAlign); }
  }

  size_t GetID() const {
    return id;
  }

  MapleSet<MeExpr *, MeExprCmp> &GetMeExprList() {
    return exprList;
  }

  const MapleSet<MeExpr *, MeExprCmp> &GetMeExprList() const {
    return exprList;
  }

  MapleVector<MeExpr *> &GetLeaderList() {
    return leaderList;
  }

  void AddLeader(MeExpr &leader) {
    DEBUG_LOG() << "Add Leader <mx" << leader.GetExprID() << "> to <vn" << this->GetID() << ">\n";
    leaderList.emplace_back(&leader);
    if (kDebug) { this->DumpLeader(kPrefixAlign); }
  }

  void Dump(size_t indent) const;

  void DumpLeader(size_t indent = 0) const;

 private:
  size_t id; // vn num
  MapleSet<MeExpr *, MeExprCmp> exprList;
  MapleVector<MeExpr *> leaderList;
};

void CongruenceClass::Dump(size_t indent) const {
  std::string space(indent, ' ');
  LogInfo::MapleLogger() << space << "vn" << id << ": { ";
  for (const MeExpr *expr : exprList) {
    LogInfo::MapleLogger() << "mx" << expr->GetExprID() << (expr == *exprList.crbegin() ? "" : ", ");
  }
  LogInfo::MapleLogger() << " }\n";
}

void CongruenceClass::DumpLeader(size_t indent) const {
  std::string space(indent, ' ');
  LogInfo::MapleLogger() << space << "Leader of vn" << id << ": { ";
  for (const MeExpr *expr : leaderList) {
    LogInfo::MapleLogger() << "mx" << expr->GetExprID() << (expr == *leaderList.crbegin() ? "" : ", ");
  }
  LogInfo::MapleLogger() << " }\n";
}
// == End of Vn

// == Start of VnExpr
enum class VnKind {
  kVnPhi, // MePhiNode
  kVnIvar, // IvarMeExpr
  kVnNary, // NaryMeExpr
  kVnOp    // OpMeExpr
};

// VnExpr is used to represent MeExpr in an vn form
class VnExpr {
 public:
  explicit VnExpr(VnKind k) : kind(k), vnExprId(kInvalidVnExprNum) {}

  virtual ~VnExpr() = default;

  VnExpr(VnKind k, size_t id) : kind(k), vnExprId(id) {}

  virtual bool IsIdentical(const VnExpr &vnExpr) {
    (void) vnExpr;
    return false;
  }

  virtual VnExpr *GetIdenticalVnExpr(VnExpr &hashedVnExpr);

  virtual size_t GetHashedIndex() {
    return 0;
  }

  VnKind GetKind() const {
    return kind;
  }

  size_t GetVnExprID() const {
    return vnExprId;
  }

  void SetVnExprID(size_t id) {
    vnExprId = id;
  }

  void SetNext(VnExpr *n) {
    next = n;
  }

  VnExpr *GetNext() {
    return next;
  }

  virtual void Dump(size_t indent) const {
    std::string space(indent, ' ');
    LogInfo::MapleLogger() << space << "vx" << vnExprId << ": " << GetKindName() << " ";
  }

 protected:
  virtual std::string GetKindName() const {
    ASSERT(false, "NYI");
    return "";
  }

 private:
  VnKind kind;
  size_t vnExprId = kInvalidVnExprNum;
  VnExpr *next = nullptr;
};

class PhiVnExpr : public VnExpr {
 public:
  PhiVnExpr(const BB &bb, MapleAllocator &alloc)
      : VnExpr(VnKind::kVnPhi), defBB(bb), opnds(alloc.Adapter()) {}
  ~PhiVnExpr() override = default;

  PhiVnExpr(size_t vnExprID, const PhiVnExpr &phiVnExpr, MapleAllocator &alloc)
      : VnExpr(VnKind::kVnPhi, vnExprID), defBB(phiVnExpr.defBB), opnds(alloc.Adapter()) {
    opnds.insert(opnds.end(), phiVnExpr.opnds.begin(), phiVnExpr.opnds.end());
  }

  void AddOpnd(const MeExpr &opnd) {
    opnds.emplace_back(&opnd);
  }

  bool IsIdentical(const VnExpr &vnExpr) override;

  size_t GetHashedIndex() override;

  const MeExpr *GetFirstOpnd() const {
    ASSERT(!opnds.empty(), "No Element in opnds when get first opnd!");
    return opnds.front();
  }

  bool HasOnlyOneOpnd() const {
    return opnds.size() == 1;
  }

  bool IsAllOpndsSame() const {
    const MeExpr *first = GetFirstOpnd();
    return std::all_of(opnds.begin() + 1, opnds.end(),
                       [first](const MeExpr *opnd) {
                         return opnd == first;
                       });
  }

  const MapleVector<const MeExpr *> &GetOpnds() const {
    return opnds;
  }

  void Dump(size_t indent) const override {
    VnExpr::Dump(indent);
    LogInfo::MapleLogger() << "{ BB" << defBB.GetBBId().GetIdx() << ", ";
    for (size_t i = 0; i < opnds.size(); ++i) {
      LogInfo::MapleLogger() << "mx" << opnds[i]->GetExprID() << (i == opnds.size() - 1 ? "" : ", ");
    }
    LogInfo::MapleLogger() << " }\n";
  }

 protected:
  std::string GetKindName() const override {
    return "VnPhi";
  }

 private:
  const BB &defBB;
  MapleVector<const MeExpr *> opnds;
};

class IvarVnExpr : public VnExpr {
 public:
  explicit IvarVnExpr(const IvarMeExpr &ivar)
      : VnExpr(VnKind::kVnIvar),
        tyIdx(ivar.GetTyIdx()),
        fldID(ivar.GetFieldID()),
        offset(ivar.GetOffset()) {}

  IvarVnExpr(size_t vnExprID, const IvarVnExpr &ivarVnExpr)
      : VnExpr(VnKind::kVnIvar, vnExprID),
        tyIdx(ivarVnExpr.tyIdx),
        fldID(ivarVnExpr.fldID),
        offset(ivarVnExpr.offset),
        baseAddr(ivarVnExpr.baseAddr),
        defStmtRank(ivarVnExpr.defStmtRank) {}

  ~IvarVnExpr() override {
    baseAddr = nullptr;
  }

  void SetBaseAddr(const CongruenceClass *baseVn) {
    baseAddr = baseVn;
  }

  void SetDefStmtRank(size_t r) {
    defStmtRank = r;
  }

  bool IsIdentical(const VnExpr &vnExpr) override;

  size_t GetHashedIndex() override;

  void Dump(size_t indent) const override {
    VnExpr::Dump(indent);
    LogInfo::MapleLogger() << "{ ";
    GlobalTables::GetTypeTable().GetTypeFromTyIdx(tyIdx)->Dump(0, false);
    LogInfo::MapleLogger() << ", fld:" << fldID << ", offset:" << offset << ", base: vn" << baseAddr->GetID()
                           << ", defStmtRank:" << defStmtRank << " }\n";
  }

 protected:
  std::string GetKindName() const override {
    return "VnIvar";
  }

 private:
  TyIdx tyIdx{0};
  FieldID fldID = 0;
  int32 offset = 0;
  const CongruenceClass *baseAddr = nullptr;
  size_t defStmtRank = 0;
};

class NaryVnExpr : public VnExpr {
 public:
  NaryVnExpr(const NaryMeExpr &nary, MapleAllocator &alloc)
      : VnExpr(VnKind::kVnNary),
        op(nary.GetOp()),
        tyIdx(nary.GetTyIdx()),
        intrinsic(nary.GetIntrinsic()),
        boundCheck(nary.GetBoundCheck()),
        opnds(alloc.Adapter()) {}

  NaryVnExpr(size_t vnExprID, const NaryVnExpr &naryVnExpr, MapleAllocator &alloc)
      : VnExpr(VnKind::kVnNary, vnExprID),
        op(naryVnExpr.op),
        tyIdx(naryVnExpr.tyIdx),
        intrinsic(naryVnExpr.intrinsic),
        boundCheck(naryVnExpr.boundCheck),
        opnds(alloc.Adapter()) {
    opnds.insert(opnds.end(), naryVnExpr.opnds.begin(), naryVnExpr.opnds.end());
  }

  ~NaryVnExpr() override = default;

  void AddOpnd(const CongruenceClass &opnd) {
    opnds.emplace_back(&opnd);
  }

  bool IsIdentical(const VnExpr &vnExpr) override;

  VnExpr *GetIdenticalVnExpr(VnExpr &hashedVnExpr) override;

  size_t GetHashedIndex() override;

  void Dump(size_t indent) const override {
    VnExpr::Dump(indent);
    LogInfo::MapleLogger() << "{ ";
    LogInfo::MapleLogger() << "op:" << kOpcodeInfo.GetTableItemAt(op).name << ", type:" << tyIdx.GetIdx();
    GlobalTables::GetTypeTable().GetTypeFromTyIdx(tyIdx)->Dump(0, false);
    LogInfo::MapleLogger() << ", intrinsic:" << GetIntrinsicName(intrinsic)
                           << ", boundCheck:" << boundCheck << ", opnds:";
    for (size_t i = 0; i < opnds.size(); ++i) {
      LogInfo::MapleLogger() << "vn" << opnds[i]->GetID() << (i == opnds.size() - 1 ? "" : ", ");
    }
    LogInfo::MapleLogger() << " }\n";
  }

 protected:
  std::string GetKindName() const override {
    return "VnNary";
  }

 private:
  Opcode op = OP_undef;
  TyIdx tyIdx{0};
  MIRIntrinsicID intrinsic;
  bool boundCheck = false;
  MapleVector<const CongruenceClass*> opnds;
};

class OpVnExpr : public VnExpr {
 public:
  OpVnExpr(const OpMeExpr &opExpr, MapleAllocator &alloc)
      : VnExpr(VnKind::kVnOp),
        op(opExpr.GetOp()),
        resType(opExpr.GetPrimType()),
        opndType(opExpr.GetOpndType()),
        bitsOffset(opExpr.GetBitsOffSet()),
        bitsSize(opExpr.GetBitsSize()),
        tyIdx(opExpr.GetTyIdx()),
        fieldID(opExpr.GetFieldID()),
        opnds(alloc.Adapter()) {}

  OpVnExpr(size_t vnExprID, const OpVnExpr &opVnExpr, MapleAllocator &alloc)
      : VnExpr(VnKind::kVnOp, vnExprID),
        op(opVnExpr.op),
        resType(opVnExpr.resType),
        opndType(opVnExpr.opndType),
        bitsOffset(opVnExpr.bitsOffset),
        bitsSize(opVnExpr.bitsSize),
        tyIdx(opVnExpr.tyIdx),
        fieldID(opVnExpr.fieldID),
        opnds(alloc.Adapter()) {
    opnds.insert(opnds.end(), opVnExpr.opnds.begin(), opVnExpr.opnds.end());
  }

  ~OpVnExpr() override = default;

  void AddOpnd(const CongruenceClass &opnd) {
    opnds.emplace_back(&opnd);
  }

  bool IsIdentical(const VnExpr &vnExpr) override;

  size_t GetHashedIndex() override;

  VnExpr *GetIdenticalVnExpr(VnExpr &hashedVnExpr) override;

  void Dump(size_t indent) const override {
    VnExpr::Dump(indent);
    LogInfo::MapleLogger() << "{ ";
    LogInfo::MapleLogger() << "op:" << kOpcodeInfo.GetTableItemAt(op).name << ", tyIdx:" << tyIdx.GetIdx()
                           << ", resType:" << GetPrimTypeName(resType) << ", opndType:" << GetPrimTypeName(opndType)
                           << ", bitsOffset:" << static_cast<int>(bitsOffset) << ", bitsSize:"
                           << static_cast<int>(bitsSize) << ", fld:" << fieldID << ", opnds:";
    for (size_t i = 0; i < opnds.size(); ++i) {
      LogInfo::MapleLogger() << "vn" << opnds[i]->GetID() << (i == opnds.size() - 1 ? "" : ", ");
    }
    LogInfo::MapleLogger() << " }\n";
  }

 protected:
  std::string GetKindName() const override {
    return "VnOp";
  }

 private:
  Opcode op = OP_undef;
  PrimType resType = kPtyInvalid;
  PrimType opndType = kPtyInvalid;  // from type
  uint8 bitsOffset = 0;
  uint8 bitsSize = 0;
  TyIdx tyIdx{0};
  FieldID fieldID = 0;
  MapleVector<const CongruenceClass *> opnds;
};

size_t PhiVnExpr::GetHashedIndex() {
  size_t seed = 0;
  std::hash_combine(seed, static_cast<uint32>(GetKind()), defBB.GetBBId().GetIdx());
  for (auto *opnd : opnds) {
    std::hash_combine(seed, opnd->GetExprID());
  }
  return seed;
}

size_t IvarVnExpr::GetHashedIndex() {
  size_t seed = 0;
  std::hash_combine(seed, static_cast<uint32>(GetKind()), tyIdx.GetIdx(), fldID, offset, baseAddr->GetID());
  return seed;
}

size_t NaryVnExpr::GetHashedIndex() {
  size_t seed = 0;
  std::hash_combine(seed, op, tyIdx.GetIdx(), intrinsic, boundCheck);
  for (auto *opnd : opnds) {
    std::hash_combine(seed, opnd->GetID());
  }
  return seed;
}

size_t OpVnExpr::GetHashedIndex() {
  size_t seed = 0;
  std::hash_combine(seed, op, resType, opndType, bitsOffset, bitsSize, tyIdx.GetIdx(), fieldID);
  for (auto *opnd : opnds) {
    std::hash_combine(seed, opnd->GetID());
  }
  return seed;
}

bool PhiVnExpr::IsIdentical(const VnExpr &vnExpr) {
  if (vnExpr.GetKind() != VnKind::kVnPhi) {
    return false;
  }
  auto &phiVnExpr = static_cast<const PhiVnExpr &>(vnExpr);
  if (phiVnExpr.defBB.GetBBId() != defBB.GetBBId() || phiVnExpr.opnds.size() != opnds.size()) {
    return false;
  }

  for (size_t i = 0; i < opnds.size(); ++i) {
    if (phiVnExpr.opnds[i] != opnds[i]) {
      return false;
    }
  }

  return true;
}

bool IvarVnExpr::IsIdentical(const VnExpr &vnExpr) {
  if (vnExpr.GetKind() != VnKind::kVnIvar) {
    return false;
  }
  auto &ivarVnExpr = static_cast<const IvarVnExpr &>(vnExpr);
  return ((ivarVnExpr.defStmtRank == defStmtRank) && ivarVnExpr.tyIdx == tyIdx &&
          ivarVnExpr.offset == offset && ivarVnExpr.fldID == fldID && ivarVnExpr.baseAddr == baseAddr);
}

bool NaryVnExpr::IsIdentical(const VnExpr &vnExpr) {
  if (vnExpr.GetKind() != VnKind::kVnNary) {
    return false;
  }
  auto &naryVnExpr = static_cast<const NaryVnExpr &>(vnExpr);
  if (op != naryVnExpr.op || tyIdx != naryVnExpr.tyIdx || intrinsic != naryVnExpr.intrinsic ||
      boundCheck != naryVnExpr.boundCheck) {
    return false;
  }
  for (size_t i = 0; i < opnds.size(); ++i) {
    if (naryVnExpr.opnds[i] != opnds[i]) {
      return false;
    }
  }

  return true;
}

VnExpr *NaryVnExpr::GetIdenticalVnExpr(VnExpr &hashedVnExpr) {
  bool isPureIntrinsic =
      op == OP_intrinsicop && IntrinDesc::intrinTable[intrinsic].IsPure();
  if (op != OP_array && !isPureIntrinsic) {
    return nullptr;
  }
  return VnExpr::GetIdenticalVnExpr(hashedVnExpr);
}

bool OpVnExpr::IsIdentical(const VnExpr &vnExpr) {
  if (vnExpr.GetKind() != VnKind::kVnOp) {
    return false;
  }
  auto &opVnExpr = static_cast<const OpVnExpr &>(vnExpr);
  if (op != opVnExpr.op || resType != opVnExpr.resType || opndType != opVnExpr.opndType ||
      bitsOffset != opVnExpr.bitsOffset || bitsSize != opVnExpr.bitsSize || tyIdx != opVnExpr.tyIdx ||
      fieldID != opVnExpr.fieldID) {
    return false;
  }
  for (size_t i = 0; i < opnds.size(); ++i) {
    if (opVnExpr.opnds[i] != opnds[i]) {
      return false;
    }
  }

  return true;
}

VnExpr *VnExpr::GetIdenticalVnExpr(VnExpr &hashedVnExpr) {
  auto *vnExpr = &hashedVnExpr;
  while (vnExpr != nullptr) {
    if (IsIdentical(*vnExpr)) {
      return vnExpr;
    }
    vnExpr = vnExpr->GetNext();
  }
  return nullptr;
}

VnExpr *OpVnExpr::GetIdenticalVnExpr(VnExpr &hashedVnExpr) {
  if (kOpcodeInfo.NotPure(op)) {
    return nullptr;
  }
  return VnExpr::GetIdenticalVnExpr(hashedVnExpr);
}
// == End of VnExpr

// == Start of GVN
constexpr size_t kTableLength = 3001;

// GVNPRE start
struct ExprDepthCmp {
  bool operator()(const MeExpr *expr1, const MeExpr *expr2) const {
    if (expr1->GetDepth() == expr2->GetDepth()) {
      return expr1->GetExprID() < expr2->GetExprID();
    }
    return expr1->GetDepth() < expr2->GetDepth();
  }
};

class BBValueInfo {
 public:
  explicit BBValueInfo(MapleAllocator &alloc) :
      availOut(alloc.Adapter()),
      anticIn(alloc.Adapter()),
      panticIn(alloc.Adapter()),
      exprGen(alloc.Adapter()),
      inserted(alloc.Adapter()) {}

  MapleSet<size_t> &GetAvailSet() {
    return availOut;
  }

  MapleSet<MeExpr *, ExprDepthCmp> &GetAnticSet() {
    return anticIn;
  }

  MapleSet<MeExpr *, ExprDepthCmp> &GetPAnticSet() {
    return panticIn;
  }

  MapleSet<MeExpr *, ExprDepthCmp> &GetExprSet() {
    return exprGen;
  }

  MapleSet<size_t> &GetInsertSet() {
    return inserted;
  }

 private:
  MapleSet<size_t> availOut;  // which values are available in current BB
  MapleSet<MeExpr *, ExprDepthCmp> anticIn;   // which values are anticipated in current BB
  MapleSet<MeExpr *, ExprDepthCmp> panticIn;   // which values are partial anticipated in current BB
  MapleSet<MeExpr *, ExprDepthCmp> exprGen;   // which values are generated in current BB
  MapleSet<size_t> inserted;   // which values are newly inserted in current BB
};
// GVNPRE end

class GVN {
 public:
  using CheckItem = std::variant<MeStmt *, const MePhiNode *>;

  struct CheckItemCmp {
    explicit CheckItemCmp(const std::map<CheckItem, size_t> &r) : rank(r) {}

    bool operator()(const CheckItem &ci1, const CheckItem &ci2) const {
      return rank.at(ci1) < rank.at(ci2);
    }

    const std::map<CheckItem, size_t> &rank;
  };

  GVN(MapleAllocator &ma, MemPool &mp, MeFunction &func, Dominance &d, Dominance &pd)
      : alloc(ma),
        tmpMP(mp),
        f(func),
        cfg(*f.GetCfg()),
        dom(d),
        pdom(pd),
        irmap(*f.GetIRMap()),
        touch(CheckItemCmp(this->rank)),
        reachableBB(f.GetCfg()->GetAllBBs().size(), false),
        hashTable(kTableLength, nullptr),
        sccTopologicalVec(ma.Adapter()),
        bbValues(f.GetCfg()->GetAllBBs().size(), nullptr) {}

  void Run();

  // try to get vn from expr2vn, return nullptr if not found
  CongruenceClass *GetVnOfMeExpr(const MeExpr &expr) const;

 private:
  // prepare
  void GenSCC();

  void RankStmtAndPhi();

  bool IsBBReachable(const BB &bb) const;

  // mark bb reachable
  void MarkBBReachable(const BB &bb);

  // mark entryBB reachable
  void MarkEntryBBReachable();

  // mark succ of bb reachable according to last stmt of bb
  void MarkSuccBBReachable(const BB &bb);
  SCCNode<BB> *GetSCCofBB(const BB *bb) const;

  // collect def-use info for SCC
  void CollectUseInfoInSCC(const SCCNode<BB> &scc);

  // Generate hashedVnExpr to hashTable
  void PushToBucket(size_t hashIdx, VnExpr *vn);

  VnExpr *HashVnExpr(VnExpr &vnExpr);

  // aux interface
  // create a new vn for meexpr, and insert to expr2vn
  CongruenceClass *CreateVnForMeExpr(MeExpr &expr);

  MeExpr *SimplifyClonedExpr(MeExpr &expr);

  size_t GetDefRankOfIvar(const IvarMeExpr &ivar);

  VnExpr *TransformExprToVnExpr(MeExpr &expr);

  // replace opnd with vn's repExpr and get vn from new expr
  CongruenceClass *GetOrCreateVnAfterTrans2VnExpr(MeExpr &expr);

  // VnExpr has an vnExprID after hashed
  CongruenceClass *GetOrCreateVnForHashedVnExpr(const VnExpr &hashedVnExpr);

  // create vn for expr and all its subexpr, return vn of expr
  // if it has no subexpr, the effect is the same as CreateVnForMeExpr
  // if its subexpr has vn created before, it will just use the vn and not create a new one.
  CongruenceClass *CreateVnForMeExprIteratively(MeExpr &expr);

  // try to get vn from expr2vn first, if not found, create a new one
  CongruenceClass *GetOrCreateVnForMeExpr(MeExpr &expr);

  CongruenceClass *GetOrCreateVnForPhi(const MePhiNode &phi, const BB &bb);

  void SetVnForExpr(MeExpr &expr, CongruenceClass &vn);

  void MarkExprNeedUpdated(const MeExpr &expr);

  BB *GetFirstReachableBB(const SCCNode<BB> &scc);

  void TouchPhisStmtsInBB(BB &bb, std::set<const BB *> &visited, const std::set<const BB *> &bbInScc);

  void TouchUseSites(const MeExpr &def, const std::set<const BB *> &visitedBB);

  // generate value number for BB(s)
  void SetIvarLhsValue(MeExpr &lhs, CongruenceClass *rhsVn);
  void GenVnForSingleBB(BB &bb);

  void GenVnForPhi(const MePhiNode &phiItem, const BB *&currBB, const std::set<const BB *> &touchedBB);

  void UpdateIvarLhsValue(MeExpr &lhs, CongruenceClass *rhsVn, bool matchToRhs);
  void GenVnForLhsValue(MeStmt &stmt, const std::set<const BB *> &touchedBB);

  void GenVnForSCCIteratively(const SCCNode<BB> &scc);

  MeExpr *GetLeaderDomExpr(MeExpr &expr, CongruenceClass &vnOfExpr, const BB &currBB);

  MeStmt *CreateLeaderAssignStmt(MeExpr &expr, CongruenceClass &vnOfExpr, BB &currBB);

  MeExpr *DoExprFRE(MeExpr &expr, MeStmt &stmt);

  bool CanPropPhi(const MePhiNode &phi) const; // firstStmt may be nullptr
  void DoPhiFRE(MePhiNode &phi, MeStmt *firstStmt); // firstStmt may be nullptr
  void FixLiveCross(MeStmt &stmt);
  bool DoStmtFREForCondStmt(CondGotoMeStmt &condStmt);
  void DoStmtFRE(MeStmt &stmt);

  void AddToVnVector(CongruenceClass &vn);
  void DumpVnVector() const;

  void DumpVnExprs() const;

  void DumpSCC(const SCCNode<BB> &scc) const;

  void DumpSCCTopologicalVec() const;

  // GVNPRE start
  void CleanSet(MapleSet<MeExpr *, ExprDepthCmp> &set) const;

  //   step 1. compute available set
  void ComputeAvail();

  void TraversalExprAvail(MeExpr &expr, const BB &curBB, BBValueInfo &bvi);

  void TraversalStmtAvail(MeStmt &stmt, BBValueInfo &bvi);

  void TraversalBBAvail(BB &bb);

  //   step 2. compute anticipated set
  void ComputeAntic();

  void RestrictPASize(MapleSet<MeExpr *, ExprDepthCmp> &pa, const std::set<MeExpr*> &paOut) const;
  void TraversalBBPartialAntic(const BB &bb);

  void TraversalBBAntic(const BB &bb, std::vector<bool> &visited);

  MeExpr *TranslatePhiForIvar(IvarMeExpr &ivar, const BB &phiBB, int32 pos, uint8 pDep);
  MeExpr *TranslatePhiForOP(OpMeExpr &op, const BB &phiBB, int32 pos, uint8 pDep);
  MeExpr *TranslatePhiForNary(NaryMeExpr &nary, const BB &phiBB, int32 pos, uint8 pDep);
  MeExpr *TranslatePhiForScalar(ScalarMeExpr &scalar, const BB &phiBB, int32 pos, uint8 pDep);
  MeExpr *TranslatePhi(MeExpr &expr, const BB &phiBB, int32 pos, uint8 pDep);

  //   step 3. insert phi
  void Insert();

  bool IsPhiValue(const MeExpr &expr, const BB &phiBB) const;

  bool IsDomValue(const MeExpr &expr, uint32 domBBID);

  RegMeExpr *ChooseReplacePreg(const MeExpr &expr, const BB &cur);
  AssignMeStmt *IVLikely(const MeExpr &expr, RegMeExpr &preg, RegMeExpr &predReg, const BB *cur, size_t pos);
  void InsertToBBPred(const MeExpr &expr, BB &cur, std::vector<std::pair<MeExpr *, bool>> &predAvail);

  void InsertForPRE(BB &curBB);

  void InsertForFRE(BB &curBB);

  //    step 4. code motion
  void CodeMotion();

  BBValueInfo *GetBBValueInfoOf(BBId id) {
    return bbValues.at(id.GetIdx());
  }

  BBValueInfo *GetBBValueInfoOf(const BB &bb) {
    return GetBBValueInfoOf(bb.GetBBId());
  }
  // GVNPRE end

  // dependencies
  MapleAllocator &alloc;
  MemPool &tmpMP;
  MeFunction &f;
  MeCFG &cfg;
  Dominance &dom;
  Dominance &pdom;
  IRMap &irmap;
  // structure for algorithm
  std::set<CheckItem, CheckItemCmp> touch; // worklist
  std::vector<bool> reachableBB;  // use bb id as key
  std::map<CheckItem, size_t> rank; // stmt/phi rank in rpo
  // vnx(key) and vny(pair.second) is congruent in BB(pair.first)
  std::map<size_t, std::vector<std::pair<const BB *, size_t>>> predicates;
  std::vector<CongruenceClass *> expr2Vn; // index is exprID
  std::vector<CongruenceClass *> vnExpr2Vn; // index is vnExprID
  std::vector<VnExpr *> hashTable;
  std::unordered_set<const MeExpr *> extraTouch; // used to collect CC.rep use
  MapleVector<SCCNode<BB> *> sccTopologicalVec;
  std::vector<CongruenceClass *> vnVector; // all vns
  std::set<MeExpr *> formals;  // used to record formals
  std::map<int32, VnExpr *> lhsIvarVnExpr;  // used to record lhsIvar's VnExpr, need update when lhs's opnd changed
  uint32 preCnt = 0;
  // GVNPRE start
  std::vector<BBValueInfo *> bbValues;  // key is bbid
  std::map<OStIdx, OriginalSt *> ost2preg;  // used to record which preg cur ost is promoted to
  // GVNPRE end
  std::set<MeStmt *> leaderCopy;  // used to record if leader has been copied
  SSACandidates cands;
};

void GVN::DumpSCC(const SCCNode<BB> &scc) const {
  auto &nodes = scc.GetNodes();
  LogInfo::MapleLogger() << "SCC " << scc.GetID() << ": { ";
  if (nodes.size() == 1) {
    LogInfo::MapleLogger() << "BB" << scc.GetNodes().front()->GetBBId().GetIdx()
                           << (scc.HasRecursion() ? "(loop)" : "(noloop)");
  } else {
    for (size_t i = 0; i < nodes.size(); ++i) {
      LogInfo::MapleLogger() << "BB" << nodes[i]->GetBBId().GetIdx() << ((i < nodes.size() - 1) ? ", " : "");
    }
  }
  LogInfo::MapleLogger() << " }\n";
}

void GVN::DumpSCCTopologicalVec() const {
  LogInfo::MapleLogger() << "-------------------\n";
  LogInfo::MapleLogger() << "---- Dump SCCs ----\n";
  LogInfo::MapleLogger() << "-------------------\n";
  for (auto *scc : sccTopologicalVec) {
    DumpSCC(*scc);
  }
  LogInfo::MapleLogger() << "-------------------\n\n";
}

void GVN::GenSCC() {
  MapleVector<BB *> &bbVec = cfg.GetAllBBs();
  size_t numOfNodes = bbVec.size();
  std::vector<BB *> allNodes;
  // copy bbVec to allNodes, but filter null BB and commonEntryBB and commonExitBB
  std::copy_if(bbVec.begin() + 2, bbVec.end(), std::inserter(allNodes, allNodes.end()), [](const BB *bb) {
    return bb != nullptr;
  });
  DEBUG_LOG() << "Building SCC\n";
  // NEEDFIX: require BB to inherit base_graph_node
  (void) BuildSCC(alloc, static_cast<uint32>(numOfNodes), allNodes, false, sccTopologicalVec, true);
  if (kDebug) {
    cfg.DumpToFile("gvn-scc");
    DumpSCCTopologicalVec();
  }
}

void GVN::RankStmtAndPhi() {
  DEBUG_LOG() << "Ranking stmts and phi of all BBs\n";
  for (auto *scc : sccTopologicalVec) {
    std::vector<BB *> rpo(scc->GetNodes().begin(), scc->GetNodes().end());
    const auto &bbId2RpoId = dom.GetReversePostOrderId();
    std::sort(rpo.begin(), rpo.end(), [&bbId2RpoId](const BB *forward, const BB *backward) {
      return bbId2RpoId[forward->GetBBId()] < bbId2RpoId[backward->GetBBId()];
    });
    for (auto *bb : rpo) {
      for (const auto &phi : std::as_const(bb->GetMePhiList())) {
        rank[phi.second] = ++kRankNum; // start from 1
      }
      for (auto &stmt : bb->GetMeStmts()) {
        rank[&stmt] = ++kRankNum;
      }
    }
  }
}

bool GVN::IsBBReachable(const BB &bb) const {
  return reachableBB[bb.GetID()];
}

void GVN::MarkBBReachable(const BB &bb) {
  if (IsBBReachable(bb) || cfg.GetCommonEntryBB() == &bb || cfg.GetCommonExitBB() == &bb) {
    return; // mark before
  }
  // mark bb itself reachable
  DEBUG_LOG() << "Mark BB" << bb.GetBBId().GetIdx() << " reachable\n";
  reachableBB[bb.GetID()] = true;
  // mark postdominantor of bb reachable
  BB *postDominantor = static_cast<BB *>(pdom.GetDom(static_cast<uint32>(bb.GetBBId().GetIdx())));
  if (postDominantor != nullptr) {
    MarkBBReachable(*postDominantor);
  }
}

void GVN::MarkEntryBBReachable() {
  BB *commenEntryBB = cfg.GetCommonEntryBB();
  ASSERT(commenEntryBB != nullptr, "cfg must have common entry BB!");
  reachableBB[commenEntryBB->GetID()] = true;
  if (!commenEntryBB->GetSucc().empty()) {
    BB *entryBB = commenEntryBB->GetSucc(0);
    ASSERT(entryBB->GetAttributes(kBBAttrIsEntry), "succ of commonEntryBB must be entry of func!");
    MarkBBReachable(*entryBB);
  }
}


void GVN::MarkSuccBBReachable(const BB &bb) {
  switch (bb.GetKind()) {
    case kBBCondGoto: {
      const MeStmt *condMeStmt = bb.GetLastMe();
      ASSERT_NOT_NULL(condMeStmt);
      MeExpr *condMeExpr = condMeStmt->GetOpnd(0);
      CongruenceClass *vn = GetVnOfMeExpr(*condMeExpr);
      const MeExpr *repExpr = vn->GetRepExpr();
      if (repExpr->GetMeOp() == kMeOpConst) {
        const BB *destBB = (repExpr->IsIntZero()) ? bb.GetSucc(condMeStmt->GetOp() == OP_brtrue ? 0 : 1)
                                                  : bb.GetSucc(condMeStmt->GetOp() == OP_brtrue ? 1 : 0);
        MarkBBReachable(*destBB);
      } else {
        MarkBBReachable(*bb.GetSucc(0));
        MarkBBReachable(*bb.GetSucc(1));
      }
      break;
    }
    case kBBSwitch: {
      auto *switchMeStmt = static_cast<const SwitchMeStmt *>(bb.GetLastMe());
      MeExpr *condMeExpr = switchMeStmt->GetOpnd(0);
      CongruenceClass *vn = GetVnOfMeExpr(*condMeExpr);
      const MeExpr *repExpr = vn->GetRepExpr();
      if (repExpr->GetMeOp() == kMeOpConst) {
        int64 val = static_cast<const ConstMeExpr *>(repExpr)->GetSXTIntValue();
        const CaseVector &cases = switchMeStmt->GetSwitchTable();
        auto it = std::find_if(cases.begin(), cases.end(), [val](const CasePair &casePair) {
          return casePair.first == val;
        });
        LabelIdx destLableIdx = (it != cases.end()) ? it->second : switchMeStmt->GetDefaultLabel();
        MarkBBReachable(*cfg.GetLabelBBAt(destLableIdx));
      } else {
        for (auto *succ : bb.GetSucc()) {
          MarkBBReachable(*succ);
        }
      }
      break;
    }
    case kBBGoto:
    case kBBFallthru:
    case kBBAfterGosub:  // the BB that follows a gosub, as it is an entry point
    case kBBIgoto: {
      for (auto *succ : bb.GetSucc()) {
        MarkBBReachable(*succ);
      }
      break;
    }
    default:
      ASSERT(bb.GetKind() == kBBReturn || bb.GetKind() == kBBNoReturn, "BB kind is not supportable");
      break;
  }
}

// NEEDFIX: Add GetSCCNode to BB
SCCNode<BB> *GVN::GetSCCofBB(const BB *bb) const {
  (void)bb;
  return nullptr;
}

void GVN::CollectUseInfoInSCC(const SCCNode<BB> &scc) {
  auto &useInfo = irmap.GetExprUseInfo();
  ASSERT(useInfo.IsInvalid(), "Require useinfo valid only for BBs in SCCNode");
  useInfo.SetState(kUseInfoOfAllExpr);
  for (BB *bb : scc.GetNodes()) {
    useInfo.CollectUseInfoInBB(bb);
  }
}

CongruenceClass *GVN::GetOrCreateVnForHashedVnExpr(const VnExpr &hashedVnExpr) {
  size_t vnExprID = hashedVnExpr.GetVnExprID();
  if (vnExprID < vnExpr2Vn.size()) {
    CongruenceClass *vn = vnExpr2Vn[vnExprID];
    ASSERT(vn != nullptr, "not set before, please check!");
    return vn;
  }
  vnExpr2Vn.resize(vnExprID + 1, nullptr);
  CongruenceClass *newVn = tmpMP.New<CongruenceClass>(alloc);
  DEBUG_LOG() << "Create new vn <vn" << newVn->GetID() << "> for vnexpr <vx" << vnExprID << ">\n";
  vnExpr2Vn[vnExprID] = newVn;
  AddToVnVector(*newVn);
  return newVn;
}

CongruenceClass *GVN::GetVnOfMeExpr(const MeExpr &expr) const {
  if (static_cast<size_t>(static_cast<uint32>(expr.GetExprID())) < expr2Vn.size()) {
    return expr2Vn[static_cast<uint32>(expr.GetExprID())];
  }
  return nullptr;
}

CongruenceClass *GVN::CreateVnForMeExpr(MeExpr &expr) {
  CongruenceClass *vn = tmpMP.New<CongruenceClass>(expr, alloc);
  DEBUG_LOG() << "Create new vn <vn" << vn->GetID() << "> for expr <mx" << expr.GetExprID() << ">\n";
  if (expr.IsScalar() && static_cast<ScalarMeExpr &>(expr).GetOst()->IsFormal()) {
    (void)formals.emplace(&expr);
  }
  SetVnForExpr(expr, *vn);
  AddToVnVector(*vn);
  return vn;
}

MeExpr *GVN::SimplifyClonedExpr(MeExpr &expr) {
  for (size_t i = 0; i < expr.GetNumOpnds(); ++i) {
    MeExpr *opnd = expr.GetOpnd(i);
    (void)GetOrCreateVnForMeExpr(*opnd);
  }
  // NEEDFIX: Simplify hashedMeExpr here
  MeExpr *hashedMeExpr = irmap.HashMeExpr(expr);
  return hashedMeExpr;
}

size_t GVN::GetDefRankOfIvar(const IvarMeExpr &ivar) {
  MeStmt *defStmt = ivar.GetDefStmt();
  if (defStmt != nullptr) {
    return rank[defStmt];
  } else {
    size_t retRank = 0;
    for (const auto *mu : ivar.GetMuList()) {
      if (mu == nullptr) { // when irmap use simplified ivar as lhs, this case happen
        return 0;
      }
      std::set<const MePhiNode *> visited;
      mu = &GetRealMu(*mu, visited);
      size_t curRank = 0;
      if (mu->IsDefByPhi()) {
        curRank = rank[mu->GetDefPhi().GetDefBB()->GetMePhiList().begin()->second];
      } else {
        curRank = rank[mu->GetDefByMeStmt()];
      }
      retRank = curRank > retRank ? curRank : retRank;
    }
    return retRank;
  }
}

VnExpr *GVN::TransformExprToVnExpr(MeExpr &expr) {
  switch (expr.GetMeOp()) {
    case kMeOpIvar: {
      auto &ivar = static_cast<IvarMeExpr &>(expr);
      IvarVnExpr vnExpr(ivar);
      MeExpr *base = ivar.GetBase();
      CongruenceClass *baseVn = GetVnOfMeExpr(*base);
      vnExpr.SetBaseAddr(baseVn);
      vnExpr.SetDefStmtRank(GetDefRankOfIvar(ivar));
      auto *hashedVnExpr = HashVnExpr(vnExpr);
      if (ivar.GetDefStmt() == nullptr) {
        return hashedVnExpr;
      }
      CongruenceClass *defVn = GetVnOfMeExpr(*ivar.GetDefStmt()->GetLHSVal());
      if (!defVn) {
        return hashedVnExpr;
      }
      if (hashedVnExpr->GetVnExprID() >= vnExpr2Vn.size()) {
        vnExpr2Vn.resize(hashedVnExpr->GetVnExprID() + 1, nullptr);
      }
      vnExpr2Vn[hashedVnExpr->GetVnExprID()] = defVn;
      return hashedVnExpr;
    }
    case kMeOpOp: {
      OpVnExpr vnExpr(static_cast<OpMeExpr &>(expr), alloc);
      for (size_t i = 0; i < expr.GetNumOpnds(); ++i) {
        MeExpr *opnd = expr.GetOpnd(i);
        CongruenceClass *opndVn = GetVnOfMeExpr(*opnd);
        vnExpr.AddOpnd(*opndVn);
      }
      return HashVnExpr(vnExpr);
    }
    case kMeOpNary: {
      NaryVnExpr vnExpr(static_cast<NaryMeExpr &>(expr), alloc);
      for (size_t i = 0; i < expr.GetNumOpnds(); ++i) {
        MeExpr *opnd = expr.GetOpnd(i);
        CongruenceClass *opndVn = GetVnOfMeExpr(*opnd);
        vnExpr.AddOpnd(*opndVn);
      }
      return HashVnExpr(vnExpr);
    }
    default:
      //  has no corresponding vnExpr
      return nullptr;
  }
}

CongruenceClass *GVN::GetOrCreateVnAfterTrans2VnExpr(MeExpr &expr) {
  VnExpr *vnExpr = TransformExprToVnExpr(expr);
  CongruenceClass *vn = nullptr;
  if (vnExpr == nullptr) {
    vn = GetVnOfMeExpr(expr);
    if (vn != nullptr) {
      return vn; // vn is found in expr2Vn
    }
    // create a new vn for expr
    vn = CreateVnForMeExpr(expr);
  } else {
    vn = GetOrCreateVnForHashedVnExpr(*vnExpr);
  }
  SetVnForExpr(expr, *vn);
  return vn;
}

CongruenceClass *GVN::CreateVnForMeExprIteratively(MeExpr &expr) {
  switch (expr.GetMeOp()) {
    case kMeOpIvar:
    case kMeOpOp:
    case kMeOpNary: {
      auto clonedMeExpr = CloneMeExpr(expr, &alloc);
      MeExpr *hashedExpr = SimplifyClonedExpr(*clonedMeExpr);
      CongruenceClass *vn = GetOrCreateVnAfterTrans2VnExpr(*hashedExpr);
      SetVnForExpr(expr, *vn);
      return vn;
    }
    case kMeOpConst: // should optimize
    case kMeOpVar:
    case kMeOpReg:
    case kMeOpAddrof:
    case kMeOpAddroffunc:
    case kMeOpAddroflabel:
    case kMeOpConststr:
    case kMeOpConststr16:
    case kMeOpSizeoftype:
    case kMeOpFieldsDist:
    case kMeOpGcmalloc: {
      return CreateVnForMeExpr(expr);
    }
    default:
      ASSERT(false, "Unknow meop, NYI!");
      return nullptr;
  }
}

CongruenceClass *GVN::GetOrCreateVnForMeExpr(MeExpr &expr) {
  CongruenceClass *vn = nullptr;
  // for non-leaf expr, its opnd's vn may changed, so we should update its opnd with new repExpr of vn,
  // and rehash to generate a new expr
  if (expr.IsLeaf()) {
    vn = GetVnOfMeExpr(expr);
    if (vn != nullptr) {
      return vn;
    }
  }
  return CreateVnForMeExprIteratively(expr);
}


void GVN::PushToBucket(size_t hashIdx, VnExpr *vn) {
  VnExpr *head = hashTable[hashIdx];
  if (head != nullptr) {
    vn->SetNext(head);
  }
  hashTable[hashIdx] = vn;
}

// Gen HashVal and get from hashTable, if not exist, generate a new one and insert to hashTable
VnExpr *GVN::HashVnExpr(VnExpr &vnExpr) {
  size_t hashIdx = vnExpr.GetHashedIndex() % kTableLength;
  VnExpr *res = hashTable[hashIdx];
  if (res != nullptr) {
    res = vnExpr.GetIdenticalVnExpr(*res);
  }
  // vnExpr has been hashed before
  if (res != nullptr) {
    return res;
  }
  // add to hashTable
  switch (vnExpr.GetKind()) {
    case VnKind::kVnIvar: {
      res = tmpMP.New<IvarVnExpr>(kVnExprNum, static_cast<IvarVnExpr &>(vnExpr));
      break;
    }
    case VnKind::kVnPhi: {
      res = tmpMP.New<PhiVnExpr>(kVnExprNum, static_cast<PhiVnExpr &>(vnExpr), alloc);
      break;
    }
    case VnKind::kVnNary: {
      res = tmpMP.New<NaryVnExpr>(kVnExprNum, static_cast<NaryVnExpr &>(vnExpr), alloc);
      break;
    }
    case VnKind::kVnOp: {
      res = tmpMP.New<OpVnExpr>(kVnExprNum, static_cast<OpVnExpr &>(vnExpr), alloc);
      break;
    }
    default:
      ASSERT(false, "NYI");
  }
  ++kVnExprNum;
  PushToBucket(hashIdx, res);
  DEBUG_LOG() << "Create new vnExpr <vx" << res->GetVnExprID() << "> :\n";
  if (kDebug) {
    res->Dump(kPrefixAlign);
  }
  return res;
}

CongruenceClass *GVN::GetOrCreateVnForPhi(const MePhiNode &phi, const BB &bb) {
  PhiVnExpr phiVn(bb, alloc);
  for (ScalarMeExpr *opnd : phi.GetOpnds()) {
    CongruenceClass *opndVn = nullptr;
    // We should generate vn for formal/init symbol when we meet it at first time.
    if (opnd->GetDefBy() == kDefByNo) {
      opndVn = GetOrCreateVnForMeExpr(*opnd);
    } else {
      opndVn = GetVnOfMeExpr(*opnd);
    }
    if (opndVn == nullptr) {
      // Here we will skip phi opnd come from backedge or unreachable edge
      continue;
    }
    const MeExpr *repExpr = opndVn->GetRepExpr();
    phiVn.AddOpnd(*repExpr);
  }
  if (phiVn.GetOpnds().empty()) {
    return nullptr;
  }
  if (phiVn.HasOnlyOneOpnd() || phiVn.IsAllOpndsSame()) {
    // if phi node has only one unique opnd, no need to hash, just return firstOpndVn
    return GetVnOfMeExpr(*phiVn.GetFirstOpnd());
  }
  VnExpr *hashedVnExpr = HashVnExpr(phiVn);
  return GetOrCreateVnForHashedVnExpr(*hashedVnExpr);
}

void GVN::SetVnForExpr(MeExpr &expr, CongruenceClass &vn) {
  if (expr2Vn.size() <= static_cast<size_t>(static_cast<uint32>(expr.GetExprID()))) {
    expr2Vn.resize(static_cast<uint32>(expr.GetExprID()) + 1, nullptr);
  }
  CongruenceClass *oldVn = expr2Vn[static_cast<uint32>(expr.GetExprID())];
  if (oldVn == &vn) {
    return;
  }
  if (oldVn != nullptr) {
    if (oldVn->GetRepExpr() == &expr && !irmap.GetExprUseInfo().IsInvalid()) {
      MeExprUseInfo &useInfo = irmap.GetExprUseInfo();
      for (auto *oldExpr : oldVn->GetMeExprList()) {
        if (!oldExpr->IsScalar()) {
          continue;
        }
        UseSitesType *useSites = useInfo.GetUseSitesOfExpr(oldExpr);
        if (useSites == nullptr) {
          continue;
        }
        for (UseItem &useItem : *useSites) {
          if (useItem.IsUseByPhi()) {
            MarkExprNeedUpdated(*oldExpr);
          }
        }
      }
    }
    oldVn->RemoveExpr(expr); // remove from oldVn
  }
  expr2Vn[static_cast<uint32>(expr.GetExprID())] = &vn;
  vn.AddExpr(expr);
}

void GVN::MarkExprNeedUpdated(const MeExpr &expr) {
  extraTouch.emplace(&expr);
}

BB *GVN::GetFirstReachableBB(const SCCNode<BB> &scc) {
  std::vector<BB *> rpo(scc.GetNodes().begin(), scc.GetNodes().end());
  const auto &bbId2RpoId = dom.GetReversePostOrderId();
  std::sort(rpo.begin(), rpo.end(), [&bbId2RpoId](const BB *forward, const BB *backward) {
    return bbId2RpoId[forward->GetBBId()] < bbId2RpoId[backward->GetBBId()];
  });
  auto it = std::find_if(rpo.begin(), rpo.end(), [this](const BB *bb) {
    return this->reachableBB[bb->GetID()];
  });
  if (it != rpo.end()) {
    return *it;
  }
  return nullptr;
}

void GVN::TouchPhisStmtsInBB(BB &bb, std::set<const BB *> &visited, const std::set<const BB *> &bbInScc) {
  if (!NeedTouchBB(bb, visited, bbInScc)) {
    return;
  }
  bool needTouchSucc = bb.GetMeStmts().empty();
  bool empty = bb.GetMePhiList().empty() && needTouchSucc;
  if (!empty) {
    DEBUG_LOG() << "Touch stmts/phis in BB" << bb.GetBBId().GetIdx() << "\n";
  }
  for (const auto &phi : std::as_const(bb.GetMePhiList())) {
    if (phi.second->GetIsLive()) {
      touch.emplace(phi.second);
      needTouchSucc = false;
    }
  }
  for (auto &stmt : bb.GetMeStmts()) {
    touch.emplace(&stmt);
  }
  if (needTouchSucc) {
    DEBUG_LOG() << "BB" << bb.GetBBId().GetIdx() << " has no stmts, touch stmts/phis in its succ\n";
    for (BB *succ : bb.GetSucc()) {
      MarkBBReachable(*succ); // currBB is reachable and has no stmt, its succ must be reachable
      TouchPhisStmtsInBB(*succ, visited, bbInScc);
    }
  }
  visited.emplace(&bb);
}

void GVN::TouchUseSites(const MeExpr &def, const std::set<const BB *> &visitedBB) {
  MeExprUseInfo &useInfo = irmap.GetExprUseInfo();
  UseSitesType *useSites = useInfo.GetUseSitesOfExpr(&def);
  if (useSites == nullptr) {
    return;
  }
  DEBUG_LOG() << "Touch use sites of expr <mx" << def.GetExprID() << ">\n";
  for (UseItem &useItem : *useSites) {
    const BB *bb = useItem.GetUseBB();
    if (!IsBBReachable(*bb) || visitedBB.count(bb) == 0) {
      continue;
    }
    if (useItem.IsUseByStmt()) {
      if (useItem.GetStmt()->GetIsLive()) {
        auto res = touch.emplace(useItem.GetStmt());
        if (res.second && useItem.GetStmt()->GetLHS() != nullptr) {
          TouchUseSites(*useItem.GetStmt()->GetLHS(), visitedBB);
        }
      }
    } else {
      if (useItem.GetPhi()->GetIsLive()) {
        auto res = touch.emplace(useItem.GetPhi());
        if (res.second) {
          TouchUseSites(*useItem.GetPhi()->GetLHS(), visitedBB);
        }
      }
    }
  }
}

void GVN::SetIvarLhsValue(MeExpr &lhs, CongruenceClass *rhsVn) {
  if (lhs.GetMeOp() != kMeOpIvar) {
    return;
  }
  auto *lhsVnExpr = TransformExprToVnExpr(lhs);
  CHECK_NULL_FATAL(lhsVnExpr);
  lhsIvarVnExpr[lhs.GetExprID()] = lhsVnExpr;
  size_t vnExprID = lhsVnExpr->GetVnExprID();
  if (vnExprID >= vnExpr2Vn.size()) {
    vnExpr2Vn.resize(vnExprID + 1, nullptr);
  }
  vnExpr2Vn[vnExprID] = rhsVn;
}

void GVN::GenVnForSingleBB(BB &bb) {
  DEBUG_LOG() << "++ Begin Generating GVN for Single BB" << bb.GetBBId().get() << "\n";
  if (!IsBBReachable(bb)) {
    DEBUG_LOG() << "BB" << bb.GetBBId().get() << " is not reachable, skip\n";
    return;
  }
  // 1. process phis
  for (const auto &phiItem : std::as_const(bb.GetMePhiList())) {
    if (!phiItem.second->GetIsLive()) {
      continue;
    }
    CongruenceClass *rhsVn = GetOrCreateVnForPhi(*phiItem.second, bb);
    SetVnForExpr(*phiItem.second->GetLHS(), *rhsVn);
  }
  // 2. process stmts
  for (auto &stmt : bb.GetMeStmts()) {
    if (!stmt.GetIsLive()) {
      continue;
    }
    // 2.1 process opnds of stmt
    for (size_t i = 0; i < stmt.NumMeStmtOpnds(); ++i) {
      MeExpr *opnd = stmt.GetOpnd(i);
      // ensure that every opnd has a vn
      (void) GetOrCreateVnForMeExpr(*opnd);
    }

    if (stmt.GetRHS() != nullptr && stmt.IsAssign()) {
      // 2.2 process lhs of stmt
      CongruenceClass *rhsVn = GetVnOfMeExpr(*stmt.GetRHS());
      MeExpr *lhs = nullptr;
      if (stmt.GetOp() == OP_iassign) {
        lhs = static_cast<const IassignMeStmt &>(stmt).GetLHSVal();
      } else {
        lhs = stmt.GetLHS();
      }
      // implicit type conversion may cause lhs and rhs not congruent
      // Example: 1) lhs : i32 <- rhs : i64;  2) lhs : bitfield (bitsSize : 1) <- rhs : i32
      MeExpr *rhs = stmt.GetRHS();
      MIRType *rhsType = rhs->GetType();
      MIRType *lhsType = lhs->GetType();
      bool typeTrunc = false;
      if (lhs->GetPrimType() != rhs->GetPrimType()) {
        rhs = irmap.CreateMeExprTypeCvt(lhs->GetPrimType(), rhs->GetPrimType(), *rhs);
        rhsVn = GetOrCreateVnForMeExpr(*rhs);
      } else if ((lhsType != nullptr && lhsType->IsMIRBitFieldType()) ||
                 (rhsType != nullptr && rhsType->IsMIRBitFieldType())) {
        typeTrunc = (lhsType != rhsType);
      }
      if (lhs->IsVolatile() || rhs->ContainsVolatile() || typeTrunc) {
        // for volatile, create an unique vn for it
        (void) GetOrCreateVnForMeExpr(*lhs);
      } else {
        SetVnForExpr(*lhs, *rhsVn);
        SetIvarLhsValue(*lhs, rhsVn);
      }
    } else if (kOpcodeInfo.IsCallAssigned(stmt.GetOp())) {
      // 2.3 process mustdef(return val) of stmt
      if (stmt.GetOp() == OP_asm) {
        auto *mustDefList = static_cast<AsmMeStmt &>(stmt).GetMustDefList();
        for (auto &item : *mustDefList) {
          MeExpr *lhs = item.GetLHS();
          if (lhs != nullptr) {
            (void) CreateVnForMeExpr(*lhs);
          }
        }
      } else {
        MeExpr *lhs = static_cast<AssignMeStmt &>(stmt).GetAssignedLHS();
        if (lhs != nullptr) {
          (void) CreateVnForMeExpr(*lhs);
        }
      }
    }
    // 2.4 process chilist of stmt
    if (stmt.GetChiList() != nullptr) {
      for (const auto &chiItem : std::as_const(*stmt.GetChiList())) {
        MeExpr *lhs = chiItem.second->GetLHS();
        CongruenceClass *lhsVn = GetVnOfMeExpr(*lhs);
        if (!lhs->IsVolatile() || lhsVn == nullptr) {
          (void) CreateVnForMeExpr(*lhs);
        }
      }
    }
  }
  // 3. set succ BB reachable according to last mestmt.
  MarkSuccBBReachable(bb);

  DEBUG_LOG() << "-- End Generating GVN for Single BB" << bb.GetBBId().get() << "\n";
}

void GVN::GenVnForPhi(const MePhiNode &phiItem, const BB *&currBB, const std::set<const BB *> &touchedBB) {
  const BB *phiBB = phiItem.GetDefBB();
  if (phiBB->IsMeStmtEmpty()) {
    currBB = phiBB;
  }
  CongruenceClass *rhsVn = GetOrCreateVnForPhi(phiItem, *phiItem.GetDefBB());
  if (rhsVn == nullptr) { // rhsVn is nullptr means all opnds have no vn
    (void) GetOrCreateVnForMeExpr(*phiItem.GetLHS());
  }
  CongruenceClass *lhsVn = GetVnOfMeExpr(*phiItem.GetLHS());
  if (rhsVn != lhsVn) { // change happened
    if (rhsVn != nullptr) {
      // remove mapping : oldLhsVn <-> lhs; and add new mapping: rhsVn <-> lhs
      SetVnForExpr(*phiItem.GetLHS(), *rhsVn);
    }
    // update touch
    TouchUseSites(*phiItem.GetLHS(), touchedBB);
  }
}

void GVN::UpdateIvarLhsValue(MeExpr &lhs, CongruenceClass *rhsVn, bool matchToRhs) {
  if (!matchToRhs || lhs.GetMeOp() != kMeOpIvar) {
    return;
  }
  auto *lhsVnExpr = TransformExprToVnExpr(lhs);
  CHECK_NULL_FATAL(lhsVnExpr);
  if (lhsIvarVnExpr[lhs.GetExprID()] != nullptr) {
    auto vnExprID = lhsIvarVnExpr[lhs.GetExprID()]->GetVnExprID();
    CongruenceClass *newVn = tmpMP.New<CongruenceClass>(alloc);
    DEBUG_LOG() << "Create new vn <vn" << newVn->GetID() << "> for vnexpr <vx" << vnExprID << ">\n";
    vnExpr2Vn[vnExprID] = newVn;
    AddToVnVector(*newVn);
  }
  lhsIvarVnExpr[lhs.GetExprID()] = lhsVnExpr;
  size_t vnExprID = lhsVnExpr->GetVnExprID();
  if (vnExprID >= vnExpr2Vn.size()) {
    vnExpr2Vn.resize(vnExprID + 1, nullptr);
  }
  vnExpr2Vn[vnExprID] = rhsVn;
}

void GVN::GenVnForLhsValue(MeStmt &stmt, const std::set<const BB *> &touchedBB) {
  MeExpr *lhs = nullptr;
  if (stmt.GetOp() == OP_iassign) {
    lhs = static_cast<const IassignMeStmt &>(stmt).GetLHSVal();
  } else {
    lhs = stmt.GetLHS();
  }
  if (stmt.GetRHS() != nullptr && lhs != nullptr) {
    CongruenceClass *rhsVn = GetVnOfMeExpr(*stmt.GetRHS());
    CongruenceClass *lhsVn = GetVnOfMeExpr(*lhs);
    // implicit type conversion may cause lhs and rhs not congruent
    // Example: 1) lhs : i32 <- rhs : i64;  2) lhs : bitfield (bitsSize : 1) <- rhs : i32
    MeExpr *rhs = stmt.GetRHS();
    MIRType *rhsType = rhs->GetType();
    MIRType *lhsType = lhs->GetType();
    bool typeTrunc = false;
    if (lhs->GetPrimType() != rhs->GetPrimType()) {
      rhs = irmap.CreateMeExprTypeCvt(lhs->GetPrimType(), rhs->GetPrimType(), *rhs);
      rhsVn = GetOrCreateVnForMeExpr(*rhs);
    } else if ((lhsType != nullptr && lhsType->IsMIRBitFieldType()) ||
               (rhsType != nullptr && rhsType->IsMIRBitFieldType())) {
      typeTrunc = (lhsType != rhsType);
    }
    bool matchToRhs = !lhs->IsVolatile() && !rhs->ContainsVolatile() && !typeTrunc;
    if (!matchToRhs) {
      CongruenceClass *vn = GetOrCreateVnForMeExpr(*lhs);
      if (vn != lhsVn) {
        TouchUseSites(*lhs, touchedBB);
      }
    } else if (rhsVn != lhsVn) {
      // remove mapping : oldLhsVn <-> lhs; and add new mapping: rhsVn <-> lhs
      SetVnForExpr(*lhs, *rhsVn);
      // update touch
      TouchUseSites(*lhs, touchedBB);
    }
    UpdateIvarLhsValue(*lhs, rhsVn, matchToRhs);
  } else if (kOpcodeInfo.IsCallAssigned(stmt.GetOp())) {
    if (stmt.GetOp() == OP_asm) {
      auto *mustDefList = static_cast<AsmMeStmt &>(stmt).GetMustDefList();
      for (auto &mustDef : *mustDefList) {
        MeExpr *mustDefLHS = mustDef.GetLHS();
        if (mustDefLHS != nullptr && GetVnOfMeExpr(*mustDefLHS) == nullptr) {
          (void) GetOrCreateVnForMeExpr(*mustDefLHS);
          TouchUseSites(*mustDefLHS, touchedBB);
        }
      }
    } else {
      MeExpr *assignedLHS = static_cast<AssignMeStmt &>(stmt).GetAssignedLHS();
      if (assignedLHS != nullptr && GetVnOfMeExpr(*assignedLHS) == nullptr) {
        (void) GetOrCreateVnForMeExpr(*assignedLHS);
        TouchUseSites(*assignedLHS, touchedBB);
      }
    }
  }
  // process chilist of stmt
  if (stmt.GetChiList() != nullptr) {
    for (const auto &chiItem : std::as_const(*stmt.GetChiList())) {
      MeExpr *chiLHS = chiItem.second->GetLHS();
      if (GetVnOfMeExpr(*chiLHS) == nullptr) {
        (void) CreateVnForMeExpr(*chiLHS);
        TouchUseSites(*chiLHS, touchedBB);
      }
    }
  }
}

void GVN::GenVnForSCCIteratively(const SCCNode<BB> &scc) {
  DEBUG_LOG() << "++ Begin Generating GVN for SCC " << scc.GetID() << "\n";
  DEBUG_LOG();
  if (kDebug) {
    DumpSCC(scc);
  }
  // 1. Init work
  // 1.2 touch stmts of first reachable BB in scc
  BB *firstBB = GetFirstReachableBB(scc);
  if (firstBB == nullptr) {
    DEBUG_LOG() << "No BB is reachable in SCC" << scc.GetID() << ", skip\n";
    return;
  }
  // when first time visit a BB in scc, touch all its stmts/phis, and record BB in touchedBB
  std::set<const BB *> touchedBB;
  // used for checking if BB is in scc.
  std::set<const BB *> bbInScc(scc.GetNodes().begin(), scc.GetNodes().end());
  TouchPhisStmtsInBB(*firstBB, touchedBB, bbInScc);
  // new useSites of changing lhsVn will be touched again
  // iterate util no new lhsVn changed and no useSites touched
  while (!touch.empty()) {
    DEBUG_LOG() << "New turn of SCC " << scc.GetID() << "\n";
    // new touched stmts/phi will be dealt with in next round
    std::vector<CheckItem> tmpTouch(touch.size());
    std::copy(touch.begin(), touch.end(), tmpTouch.begin());
    touch.clear();
    for (auto &item : tmpTouch) {
      const BB *currBB = nullptr;
      if (std::holds_alternative<const MePhiNode *>(item)) {
        // 2. process phinode
        const MePhiNode *phiItem = std::get<const MePhiNode *>(item);
        GenVnForPhi(*phiItem, currBB, touchedBB);
      } else if (std::get<MeStmt*>(item)->GetIsLive()) {
        // 3. process stmt
        MeStmt *stmt = std::get<MeStmt *>(item);
        // 3.1 process opnds of stmt
        for (size_t i = 0; i < stmt->NumMeStmtOpnds(); ++i) {
          MeExpr *opnd = stmt->GetOpnd(i);
          (void) GetOrCreateVnForMeExpr(*opnd);
        }
        // 3.2 process lhs of stmt
        GenVnForLhsValue(*stmt, touchedBB);
        const BB *stmtBB = stmt->GetBB();
        currBB = stmtBB->GetLastMe() == stmt ? stmtBB : currBB;
        if (currBB && currBB->GetKind() == kBBCondGoto &&
            (stmt->GetOpnd(0)->GetOp() == OP_eq || stmt->GetOpnd(0)->GetOp() == OP_ne)) {
          // 4. generate condition predicates
          CongruenceClass *vnx = GetVnOfMeExpr(*stmt->GetOpnd(0)->GetOpnd(0));
          CongruenceClass *vny = GetVnOfMeExpr(*stmt->GetOpnd(0)->GetOpnd(1));
          ASSERT(vnx != nullptr, "should have found CC.");
          ASSERT(vny != nullptr, "should have found CC.");
          auto vnxID = std::min(vnx->GetID(), vny->GetID());
          auto vnyID = std::max(vnx->GetID(), vny->GetID());
          predicates[vnxID].emplace_back(
              currBB->GetSucc(static_cast<size_t>(stmt->GetOpnd(0)->GetOp() == OP_eq)), vnyID);
        }
      }
      if (currBB != nullptr) {
        // 5. set succ BB reachable according to last mestmt.
        MarkSuccBBReachable(*currBB); // not all succ will be mark reachable
        for (BB *succ : currBB->GetSucc()) {
          if (IsBBReachable(*succ) && NeedTouchBB(*succ, touchedBB, bbInScc)) {
            TouchPhisStmtsInBB(*succ, touchedBB, bbInScc);
          }
        }
        for (BB *pred : currBB->GetPred()) {
          if (IsBBReachable(*pred) && NeedTouchBB(*pred, touchedBB, bbInScc)) {
            TouchPhisStmtsInBB(*pred, touchedBB, bbInScc);
          }
        }
      }
    }
    if (!extraTouch.empty()) {
      for (auto *extra : extraTouch) {
        TouchUseSites(*extra, touchedBB);
      }
      extraTouch.clear();
    }
  }
  DEBUG_LOG() << "-- End Generating GVN for SCC " << scc.GetID() << "\n";
}

void GVN::AddToVnVector(CongruenceClass &vn) {
  if (vnVector.size() <= vn.GetID()) {
    vnVector.resize(vn.GetID() + 1, nullptr);
  }
  vnVector[vn.GetID()] = &vn;
}

void GVN::DumpVnVector() const {
  LogInfo::MapleLogger() << "-------------------\n";
  LogInfo::MapleLogger() << "--- Dump All Vn ---\n";
  LogInfo::MapleLogger() << "-------------------\n";
  for (const CongruenceClass *vn : vnVector) {
    vn->Dump(0);
  }
  LogInfo::MapleLogger() << "-------------------\n\n";
}

void GVN::DumpVnExprs() const {
  LogInfo::MapleLogger() << "-------------------\n";
  LogInfo::MapleLogger() << "-- Dump VnExprs ---\n";
  LogInfo::MapleLogger() << "-------------------\n";
  constexpr size_t indent = 2;
  for (size_t i = 0; i < hashTable.size(); ++i) {
    VnExpr *vnExpr = hashTable[i];
    if (vnExpr != nullptr) {
      LogInfo::MapleLogger() << "HashTable[" << i << "]:\n";
    }
    while (vnExpr != nullptr) {
      vnExpr->Dump(indent);
      vnExpr = vnExpr->GetNext();
    }
  }
  LogInfo::MapleLogger() << "-------------------\n\n";
}

// create an assign stmt from expr to a new tmp reg
MeStmt *GVN::CreateLeaderAssignStmt(MeExpr &expr, CongruenceClass &vnOfExpr, BB &currBB) {
  // create a tmp reg as leader
  RegMeExpr *leader = irmap.CreateRegMeExpr(expr.GetPrimType());
  MeStmt *regAss = irmap.CreateAssignMeStmt(*leader, expr, currBB);
  vnOfExpr.AddLeader(*leader);
  return regAss;
}

MeExpr *GVN::GetLeaderDomExpr(MeExpr &expr, CongruenceClass &vnOfExpr, const BB &currBB) {
  auto &leaderVec = vnOfExpr.GetLeaderList();
  if (expr.GetMeOp() == kMeOpConst) {
    if (leaderVec.empty()) {
      vnOfExpr.AddLeader(expr);
    }
    if (leaderVec.front() != &expr) {
      leaderVec.back() = leaderVec.front();
      leaderVec.front() = &expr;
    }
    return &expr;
  }
  for (size_t i = 0; i < leaderVec.size(); ++i) {
    MeExpr *cand = leaderVec[i];
    if (cand->IsScalar()) {
      auto *scalar = static_cast<ScalarMeExpr *>(cand);
      BB *defBB = scalar->DefByBB();
      if (dom.Dominate(*defBB, currBB)) {
        return scalar;
      }
      // formal dominance every BB
      if (scalar->IsZeroVersion() && scalar->GetOst()->IsFormal()) {
        return scalar;
      }
    } else if (cand->GetMeOp() == kMeOpIvar) {
      ASSERT(false, "Ivar should never be a leader!");
      return nullptr;
    } else if (cand->GetMeOp() == kMeOpConst) {
      if (i != 0) {
        // make first leader as const (we may keep only one leader if it is const)
        leaderVec[i] = leaderVec[0];
        leaderVec[0] = cand;
      }
      return cand;
    }
  }
  return nullptr;
}

MeExpr *GVN::DoExprFRE(MeExpr &expr, MeStmt &stmt) {
  if (preCnt >= MeOption::gvnpreLimit) {
    return &expr;
  }
  if (expr.GetMeOp() == kMeOpConststr || expr.GetMeOp() == kMeOpConststr16) {
    return &expr;
  }
  preCnt++;
  if (expr.IsVolatile()) {
    if (expr.GetMeOp() == kMeOpIvar) {
      std::unique_ptr<MeExpr> clonedExpr = CloneMeExpr(expr, &alloc);
      MeExpr *base = expr.GetOpnd(0);
      MeExpr *res = DoExprFRE(*base, stmt);
      if (res != base) {
        static_cast<IvarMeExpr &>(*clonedExpr).SetBase(res);
      }
      return irmap.HashMeExpr(*clonedExpr);
    }
    return &expr;
  }
  CongruenceClass *exprVn = GetVnOfMeExpr(expr);
  CHECK_FATAL(exprVn != nullptr, "Vn for expr mx%d is not set before!", expr.GetExprID());
  BB *currBB = stmt.GetBB();
  MeExpr *leader = GetLeaderDomExpr(expr, *exprVn, *currBB);
  if (leader != nullptr) {
    // check if leader can be replaced with same reg ost to promote prop
    if (expr.GetMeOp() == kMeOpReg && leader->GetMeOp() == kMeOpReg) {
      auto *rhs = static_cast<ScalarMeExpr*>(leader)->GetDefStmt()->GetRHS();
      if (rhs && rhs->GetMeOp() == kMeOpReg &&
          static_cast<RegMeExpr*>(rhs)->GetOst() == static_cast<RegMeExpr&>(expr).GetOst()) {
        return &expr;
      }
    }
    return leader;
  }
  std::unique_ptr<MeExpr> clonedExpr = CloneMeExpr(expr, &alloc);
  MeExpr *newExpr = &expr;
  if (clonedExpr != nullptr) {
    // FRE for opnd of expr
    for (size_t i = 0; i < expr.GetNumOpnds(); ++i) {
      MeExpr *opnd = expr.GetOpnd(i);
      MeExpr *repOpnd = DoExprFRE(*opnd, stmt);
      if (repOpnd != opnd && clonedExpr->GetMeOp() == kMeOpIvar) {
        static_cast<IvarMeExpr &>(*clonedExpr).SetBase(repOpnd);
      } else if (repOpnd != opnd) {
        clonedExpr->SetOpnd(i, repOpnd);
      }
    }
    newExpr = irmap.HashMeExpr(*clonedExpr);
    auto *simplified = irmap.SimplifyMeExpr(newExpr);
    newExpr = simplified ? simplified : newExpr;
  }
  // we may create a tmp symbol for agg later
  if (newExpr->GetPrimType() == PTY_agg || newExpr->ContainsVolatile()) {
    return newExpr;
  }
  if (newExpr->IsScalar() && static_cast<ScalarMeExpr *>(newExpr)->IsDefByNo() &&
      static_cast<ScalarMeExpr *>(newExpr)->GetOst()->IsFormal()) {
    BB *entryBB = cfg.GetCommonEntryBB()->GetSucc(0);
    CHECK_FATAL(entryBB->GetPred().empty(), "should be empty");
    MeStmt *newStmt = CreateLeaderAssignStmt(*newExpr, *exprVn, *entryBB);
    entryBB->AddMeStmtFirst(newStmt);
    return newStmt->GetLHS();
  }
  // Create tmp reg to store the result of expr and return this reg
  MeStmt *newStmt = CreateLeaderAssignStmt(*newExpr, *exprVn, *currBB);
  currBB->InsertMeStmtBefore(&stmt, newStmt);
  return newStmt->GetLHS();
}

bool GVN::CanPropPhi(const MePhiNode &phi) const {
  ScalarMeExpr *lhs = phi.GetLHS();
  if (lhs->GetMeOp() != kMeOpReg || lhs->GetOst()->GetIndirectLev() != 0) {
    return false;
  }
  // check phi opnds
  OStIdx first = OStIdx(0);
  for (auto *opnd : phi.GetOpnds()) {
    if (!opnd->IsDefByStmt() || !opnd->GetDefStmt()->GetRHS() || opnd->GetDefStmt()->GetRHS()->GetMeOp() != kMeOpReg) {
      return false;
    }
    auto *rhs = static_cast<ScalarMeExpr *>(opnd->GetDefStmt()->GetRHS());
    first = first == 0 ? rhs->GetOstIdx() : first;
    if (rhs->GetOstIdx() != first) {
      return false;
    }
  }
  // check new phi
  auto &allPhis = phi.GetDefBB()->GetMePhiList();
  auto found = allPhis.find(first);
  if (found == allPhis.end()) {
    return false;
  }
  return found->second->GetIsLive();
}

void GVN::DoPhiFRE(MePhiNode &phi, MeStmt *firstStmt) {
  if (preCnt >= MeOption::gvnpreLimit) {
    return;
  }
  preCnt++;
  ScalarMeExpr *lhs = phi.GetLHS();
  // skip agg phi because it needs multiple dassign
  // also skip indirect value
  if (lhs->GetPrimType() == PTY_agg || lhs->GetOst()->GetIndirectLev() != 0 ||
      (!lhs->GetOst()->GetType()->IsScalarType() && !lhs->GetOst()->GetType()->IsMIRPtrType())) {
    return;
  }
  CongruenceClass *vn = GetVnOfMeExpr(*lhs);
  ASSERT(vn != nullptr, "Vn for phi mx%d is not set before!", lhs->GetExprID());
  BB *currBB = phi.GetDefBB();
  MeExpr *leader = GetLeaderDomExpr(*lhs, *vn, *currBB);
  if (leader != nullptr) {
    return;
  }
  if (IsPhiValue(*lhs, *currBB) && lhs->GetMeOp() != kMeOpReg) {
    return;
  }
  if (CanPropPhi(phi)) {
    return;
  }
  MeStmt *assignStmt = CreateLeaderAssignStmt(*lhs, *vn, *currBB);
  // if firstStmt is nullptr, means currBB has no stmt, insert stmt at last
  // otherwise, insert assign stmt before firstStmt
  if (firstStmt == nullptr) {
    currBB->AddMeStmtLast(assignStmt);
  } else {
    currBB->InsertMeStmtBefore(firstStmt, assignStmt);
  }
}

bool OpndsContainsOst(const MeExpr &expr, OriginalSt *ost) {
  if (expr.IsScalar() && static_cast<const ScalarMeExpr&>(expr).GetOst() == ost) {
    return true;
  }
  for (uint8 i = 0; i < expr.GetNumOpnds(); i++) {
    if (OpndsContainsOst(*expr.GetOpnd(i), ost)) {
      return true;
    }
  }
  return false;
}

void GVN::FixLiveCross(MeStmt &stmt) {
  // fix reg live cross
  if (stmt.GetOp() == OP_regassign) {
    auto *rhs = stmt.GetRHS();
    if (rhs->GetMeOp() != kMeOpReg) {
      return;
    }
    auto *leaderDef = static_cast<ScalarMeExpr *>(rhs)->GetDefByMeStmt();
    if (leaderDef != stmt.GetPrev()) {
      return;
    }
    auto *origLhs = stmt.GetLHS();
    CHECK_FATAL(origLhs != nullptr, "DoStmtFRE : check assign stmt");
    CHECK_NULL_FATAL(leaderDef);
    stmt.SetOpnd(0, leaderDef->GetRHS());
    leaderDef->SetOpnd(0, origLhs);
    leaderDef->GetBB()->RemoveMeStmt(leaderDef);
    stmt.GetBB()->InsertMeStmtAfter(&stmt, leaderDef);
  }
  // use lhsVar's recorded reg ost to get better prop
  auto *rhs = stmt.GetRHS();
  if (!rhs || rhs->GetMeOp() != kMeOpReg || static_cast<ScalarMeExpr*>(rhs)->IsDefByNo()) {
    return;
  }
  auto *leaderDef = static_cast<ScalarMeExpr*>(rhs)->GetDefByMeStmt();
  auto *prev = stmt.GetPrev();
  if (!leaderDef || !prev || leaderDef->GetBB() != prev->GetBB() || leaderCopy.count(leaderDef) != 0) {
    return;
  }
  auto *lhs = stmt.GetLHS();
  if (ost2preg.find(lhs->GetOstIdx()) == ost2preg.end()) {
    return;
  }
  auto *regOst = ost2preg.find(lhs->GetOstIdx())->second;
  while (leaderDef != prev) {
    for (size_t k = 0; k < prev->NumMeStmtOpnds(); ++k) {
      if (OpndsContainsOst(*prev->GetOpnd(k), regOst)) {
        return;
      }
    }
    prev = prev->GetPrev();
    if (!prev) {
      return;
    }
  }
  auto *pregVersion = irmap.CreateRegMeExprVersion(*regOst);
  static_cast<AssignMeStmt*>(leaderDef)->SetLHS(pregVersion);
  pregVersion->SetDefByStmt(*leaderDef);
  MeSSAUpdate::InsertOstToSSACands(pregVersion->GetOstIdx(), *pregVersion->DefByBB(), &cands);
  auto *newLeaderDef = irmap.CreateAssignMeStmt(static_cast<ScalarMeExpr&>(*rhs), *pregVersion, *leaderDef->GetBB());
  leaderDef->GetBB()->InsertMeStmtAfter(leaderDef, newLeaderDef);
  (void)leaderCopy.emplace(newLeaderDef);
}

bool GVN::DoStmtFREForCondStmt(CondGotoMeStmt &condStmt) {
  auto *condOpnd = condStmt.GetOpnd();
  if (!kOpcodeInfo.IsCompare(condOpnd->GetOp())) {
    return false;
  }
  std::unique_ptr<MeExpr> clonedExpr = CloneMeExpr(*condOpnd, &alloc);
  for (size_t j = 0; j < clonedExpr->GetNumOpnds(); j++) {
    MeExpr *opnd = clonedExpr->GetOpnd(j);
    MeExpr *repOpnd = DoExprFRE(*opnd, condStmt);
    if (repOpnd != opnd) {
      clonedExpr->SetOpnd(j, repOpnd);
    }
  }
  MeExpr *hashed = irmap.HashMeExpr(*clonedExpr);
  MeExpr *simplified = irmap.SimplifyMeExpr(hashed);
  condStmt.SetOpnd(0, simplified ? simplified : hashed);
  return true;
}

void GVN::DoStmtFRE(MeStmt &stmt) {
  if (preCnt >= MeOption::gvnpreLimit) {
    return;
  }
  if (stmt.GetOp() == OP_asm) {
    return;
  }
  if (stmt.GetOp() == OP_brfalse || stmt.GetOp() == OP_brtrue) {
    bool done = DoStmtFREForCondStmt(static_cast<CondGotoMeStmt&>(stmt));
    if (done) {
      return;
    }
  }
  for (size_t i = 0; i < stmt.NumMeStmtOpnds(); ++i) {
    MeExpr *opnd = stmt.GetOpnd(i);
    MeExpr *repOpnd = DoExprFRE(*opnd, stmt);
    if (repOpnd != opnd) {
      if (i == 0 && stmt.GetOp() == OP_iassign) {
        auto &iassign = static_cast<IassignMeStmt &>(stmt);
        IvarMeExpr *newLhs = irmap.BuildLHSIvar(*repOpnd, iassign, iassign.GetLHSVal()->GetFieldID());
        newLhs->SetVolatileFromBaseSymbol(iassign.GetLHSVal()->GetVolatileFromBaseSymbol());
        iassign.SetLHSVal(newLhs);
        continue;
      }
      auto *simplified = irmap.SimplifyMeExpr(repOpnd);
      repOpnd = simplified ? simplified : repOpnd;
      stmt.SetOpnd(i, repOpnd);
    } else {
      continue;
    }
    if (stmt.GetOp() != OP_regassign && stmt.GetOp() != OP_dassign) {
      continue;
    }
    FixLiveCross(stmt);
  }
}

// GVNPRE start
const GVN *curGVN = nullptr;
PregIdx gvnInsStart = INT32_MAX;
struct ExprVnCmp {
  bool operator() (const MeExpr *expr1, const MeExpr *expr2) const {
    return curGVN->GetVnOfMeExpr(*expr1) < curGVN->GetVnOfMeExpr(*expr2);
  }
};

void GVN::CleanSet(MapleSet<MeExpr *, ExprDepthCmp> &set) const {
  curGVN = this;
  std::set<MeExpr *, ExprVnCmp> cleaned(set.begin(), set.end());
  set.clear();
  set.insert(cleaned.begin(), cleaned.end());
  curGVN = nullptr;
}

void GVN::TraversalExprAvail(MeExpr &expr, const BB &curBB, BBValueInfo &bvi) {
  if (expr.GetPrimType() == PTY_agg) {
    return;
  }
  if (!GetVnOfMeExpr(expr)) {
    return;
  }
  switch (expr.GetMeOp()) {
    case kMeOpOp: {
      auto &meOpExpr = static_cast<OpMeExpr&>(expr);
      for (uint32 i = 0; i < meOpExpr.GetNumOpnds(); i++) {
        TraversalExprAvail(*meOpExpr.GetOpnd(i), curBB, bvi);
      }
      break;
    }
    case kMeOpNary: {
      auto &naryMeExpr = static_cast<NaryMeExpr&>(expr);
      const MapleVector<MeExpr*> &opnds = naryMeExpr.GetOpnds();
      for (auto it = opnds.begin(); it != opnds.end(); ++it) {
        TraversalExprAvail(**it, curBB, bvi);
      }
      break;
    }
    case kMeOpIvar: {
      auto &ivarMeExpr = static_cast<IvarMeExpr&>(expr);
      TraversalExprAvail(*ivarMeExpr.GetBase(), curBB, bvi);
      if (ivarMeExpr.GetDefStmt() && ivarMeExpr.GetDefStmt()->GetBB() == &curBB) {
        bvi.GetAvailSet().emplace(GetVnOfMeExpr(expr)->GetID());
        return;
      }
      for (auto *mu : ivarMeExpr.GetMuList()) {
        if (!mu || mu->IsDefByPhi() || mu->DefByBB() != &curBB) {
          bvi.GetExprSet().emplace(&expr);
          break;
        }
      }
      bvi.GetAvailSet().emplace(GetVnOfMeExpr(expr)->GetID());
      return;
    }
    case kMeOpVar: {
      auto &var = static_cast<ScalarMeExpr&>(expr);
      if (!var.IsDefByPhi() && var.DefByBB() == &curBB) {
        bvi.GetAvailSet().emplace(GetVnOfMeExpr(expr)->GetID());
        return;
      }
      break;
    }
    case kMeOpAddrof:
    case kMeOpAddroffunc:
    case kMeOpAddroflabel:
      break;
    case kMeOpReg:
    case kMeOpGcmalloc:
    case kMeOpConst:
    case kMeOpConststr:
    case kMeOpConststr16:
    case kMeOpSizeoftype:
    case kMeOpFieldsDist: {
      bvi.GetAvailSet().emplace(GetVnOfMeExpr(expr)->GetID());
      return;
    }
    default:
      CHECK_FATAL(false, "MeOP NIY");
  }
  bvi.GetAvailSet().emplace(GetVnOfMeExpr(expr)->GetID());
  bvi.GetExprSet().emplace(&expr);
}

void GVN::TraversalStmtAvail(MeStmt &stmt, BBValueInfo &bvi) {
  switch (stmt.GetOp()) {
    case OP_jstry:
    case OP_jscatch:
    case OP_finally:
    case OP_endtry:
    case OP_cleanuptry:
    case OP_try:
    case OP_catch:
    case OP_goto:
    case OP_comment:
    case OP_gosub:
    case OP_retsub:
      break;
    case OP_iassign:
    case OP_iassignoff: {
      auto &ivarStmt = static_cast<const IassignMeStmt&>(stmt);
      TraversalExprAvail(*ivarStmt.GetRHS(), *stmt.GetBB(), bvi);
      TraversalExprAvail(*ivarStmt.GetLHSVal()->GetBase(), *stmt.GetBB(), bvi);
      if (ivarStmt.GetRHS()->ContainsVolatile()) {
        TraversalExprAvail(*ivarStmt.GetLHSVal(), *stmt.GetBB(), bvi);
      }
      break;
    }
    case OP_brtrue:
    case OP_brfalse: {
      auto &condGotoStmt = static_cast<const CondGotoMeStmt&>(stmt);
      auto *condOpnd = condGotoStmt.GetOpnd();
      if (kOpcodeInfo.IsCompare(condOpnd->GetOp())) {
        for (size_t i = 0; i < condOpnd->GetNumOpnds(); i++) {
          TraversalExprAvail(*condOpnd->GetOpnd(i), *stmt.GetBB(), bvi);
        }
      } else {
        TraversalExprAvail(*condOpnd, *stmt.GetBB(), bvi);
      }
      break;
    }
    case OP_switch: {
      auto &switchStmt = static_cast<const SwitchMeStmt&>(stmt);
      TraversalExprAvail(*switchStmt.GetOpnd(), *stmt.GetBB(), bvi);
      break;
    }
    case OP_dassign: {
      auto &dassMeStmt = static_cast<const DassignMeStmt&>(stmt);
      TraversalExprAvail(*dassMeStmt.GetRHS(), *stmt.GetBB(), bvi);
      if (dassMeStmt.GetRHS()->ContainsVolatile()) {
        TraversalExprAvail(*dassMeStmt.GetLHS(), *stmt.GetBB(), bvi);
      }
      break;
    }
    case OP_regassign: {
      auto &rassMeStmt = static_cast<const AssignMeStmt&>(stmt);
      TraversalExprAvail(*rassMeStmt.GetRHS(), *stmt.GetBB(), bvi);
      if (rassMeStmt.GetRHS()->ContainsVolatile()) {
        TraversalExprAvail(*rassMeStmt.GetLHS(), *stmt.GetBB(), bvi);
      }
      break;
    }
    case OP_eval:
    case OP_igoto:
    CASE_OP_ASSERT_NONNULL
    case OP_free: {
      auto &unaryStmt = static_cast<const UnaryMeStmt&>(stmt);
      TraversalExprAvail(*unaryStmt.GetOpnd(), *stmt.GetBB(), bvi);
      break;
    }
    case OP_return: {
      auto &retMeStmt = static_cast<const RetMeStmt&>(stmt);
      const MapleVector<MeExpr*> &opnds = retMeStmt.GetOpnds();
      for (auto it = opnds.begin(); it != opnds.end(); ++it) {
        TraversalExprAvail(**it, *stmt.GetBB(), bvi);
      }
      break;
    }
    case OP_call:
    case OP_virtualcall:
    case OP_virtualicall:
    case OP_superclasscall:
    case OP_interfacecall:
    case OP_interfaceicall:
    case OP_customcall:
    case OP_polymorphiccall:
    case OP_icall:
    case OP_icallproto:
    case OP_callassigned:
    case OP_virtualcallassigned:
    case OP_virtualicallassigned:
    case OP_superclasscallassigned:
    case OP_interfacecallassigned:
    case OP_interfaceicallassigned:
    case OP_customcallassigned:
    case OP_polymorphiccallassigned:
    case OP_icallassigned:
    case OP_icallprotoassigned:
    case OP_asm:
    case OP_intrinsiccall:
    case OP_xintrinsiccall:
    case OP_intrinsiccallwithtype:
    case OP_intrinsiccallassigned:
    case OP_xintrinsiccallassigned:
    case OP_intrinsiccallwithtypeassigned: {
      auto &naryMeStmt = static_cast<const NaryMeStmt&>(stmt);
      const MapleVector<MeExpr*> &opnds = naryMeStmt.GetOpnds();
      for (auto it = opnds.begin(); it != opnds.end(); ++it) {
        TraversalExprAvail(**it, *stmt.GetBB(), bvi);
      }
      break;
    }
    CASE_OP_ASSERT_BOUNDARY {
      auto &assMeStmt = static_cast<const NaryMeStmt&>(stmt);
      TraversalExprAvail(*assMeStmt.GetOpnd(0), *stmt.GetBB(), bvi);
      TraversalExprAvail(*assMeStmt.GetOpnd(1), *stmt.GetBB(), bvi);
      break;
    }
    default:
      CHECK_FATAL(false, "unsupported opcode");
      break;
  }
  if (kOpcodeInfo.IsCallAssigned(stmt.GetOp())) {
    MapleVector<MustDefMeNode> *mustDefList = stmt.GetMustDefList();
    auto it = mustDefList->begin();
    size_t i = 0; // count for inline asm out put constraints
    bool isAsm = stmt.GetOp() == OP_asm;
    for (; it != mustDefList->end(); ++it) {
      if ((*it).GetLHS()->GetMeOp() != kMeOpVar || (*it).GetLHS()->GetPrimType() == PTY_agg) {
        continue;
      }
      if (!isAsm) {
        auto *vn = GetVnOfMeExpr(*(*it).GetLHS());
        CHECK_NULL_FATAL(vn);
        bvi.GetAvailSet().emplace(vn->GetID());
        continue;
      }
      const std::string &str = GlobalTables::GetUStrTable().GetStringFromStrIdx(
          static_cast<const AsmMeStmt&>(stmt).outputConstraints[i++]);
      // skip memory access in inline asm
      if (str.find("Q") != std::string::npos || str.find("m") != std::string::npos) {
        continue;
      }
      auto *vn = GetVnOfMeExpr(*(*it).GetLHS());
      CHECK_NULL_FATAL(vn);
      bvi.GetAvailSet().emplace(vn->GetID());
    }
  }
}

bool HasRealDef(const MePhiNode &phi, std::set<const MePhiNode*> &visited) {
  if (visited.count(&phi) != 0) {
    return false;
  }
  visited.emplace(&phi);
  for (auto *opnd : phi.GetOpnds()) {
    switch (opnd->GetDefBy()) {
      case kDefByNo: {
        if (opnd->GetOst()->IsFormal()) {
          return true;
        }
        break;
      }
      case kDefByMustDef:
      case kDefByStmt: {
        return true;
      }
      case kDefByChi: {
        break;
      }
      case kDefByPhi: {
        if (HasRealDef(opnd->GetDefPhi(), visited)) {
          return true;
        }
        break;
      }
    }
  }
  return false;
}

void GVN::TraversalBBAvail(BB &bb) {
  if (!IsBBReachable(bb)) {
    return;
  }
  auto *curBVI = tmpMP.New<BBValueInfo>(alloc);
  bbValues[bb.GetID()] = curBVI;
  if (&bb == cfg.GetCommonEntryBB()) {
    // push param as avail_out
    for (auto *expr : formals) {
      auto *vn = GetVnOfMeExpr(*expr);
      if (vn) {
        (void)curBVI->GetAvailSet().emplace(vn->GetID());
      }
    }
  } else {
    // push dominator's avail_out
    auto &domAvail = bbValues[dom.GetDom(bb.GetID())->GetID()]->GetAvailSet();
    curBVI->GetAvailSet().insert(domAvail.begin(), domAvail.end());
  }
  // push phiGen
  for (auto const &it : bb.GetMePhiList()) {
    if (!it.second->GetIsLive()) {
      continue;
    }
    auto *lhs = it.second->GetLHS();
    // skip agg phi because it needs multiple dassign
    // also skip indirect value
    if (lhs->GetPrimType() == PTY_agg || lhs->GetOst()->GetIndirectLev() != 0 ||
        (!lhs->GetOst()->GetType()->IsScalarType() && !lhs->GetOst()->GetType()->IsMIRPtrType())) {
      continue;
    }
    // We need to check phi's opnds, and if none of them are defined by real def,
    // that means such phi lhs can not be available by cur phi def. Note that reg
    // always has real def.
    std::set<const MePhiNode*> visited;
    if (lhs->GetMeOp() == kMeOpVar && !HasRealDef(*it.second, visited)) {
      continue;
    }
    auto *lhsVn = GetVnOfMeExpr(*lhs);
    if (lhsVn) {
      (void)curBVI->GetAvailSet().emplace(lhsVn->GetID());
    }
    if (lhs->GetMeOp() == kMeOpVar) {
      curBVI->GetExprSet().emplace(lhs);
    }
  }
  // push valueGen
  for (auto &it : bb.GetMeStmts()) {
    TraversalStmtAvail(it, *curBVI);
  }
  auto &domChildren = dom.GetDomChildren(bb.GetID());
  for (auto &childbbid : std::as_const(domChildren)) {
    TraversalBBAvail(*cfg.GetBBFromID(BBId(childbbid)));
  }
}

void GVN::ComputeAvail() {
  TraversalBBAvail(*cfg.GetCommonEntryBB());
}

MeExpr *GVN::TranslatePhiForIvar(IvarMeExpr &ivar, const BB &phiBB, int32 pos, uint8 pDep) {
  auto *newBase = TranslatePhi(*ivar.GetBase(), phiBB, pos, pDep + 1);
  if (!newBase) {
    return nullptr;
  }
  CongruenceClass *baseVn = GetVnOfMeExpr(*newBase);
  if (baseVn == nullptr) {
    return nullptr;
  }
  IvarVnExpr vnExpr(ivar);
  vnExpr.SetBaseAddr(baseVn);
  ivar.SetBase(newBase);
  for (auto *mu : ivar.GetMuList()) {
    if (!mu) {
      continue;
    }
    auto *newMu = TranslatePhi(*mu, phiBB, pos, 0);
    if (!newMu || !newMu->IsScalar()) {
      return nullptr;
    }
    ivar.SetMuItem(0, static_cast<ScalarMeExpr*>(newMu));
  }
  vnExpr.SetDefStmtRank(GetDefRankOfIvar(ivar));
  auto *hashed = irmap.HashMeExpr(ivar);
  if (GetVnOfMeExpr(*hashed)) {
    return hashed;
  }
  (void)GetOrCreateVnAfterTrans2VnExpr(*hashed);
  return hashed;
}

MeExpr *GVN::TranslatePhiForOP(OpMeExpr &op, const BB &phiBB, int32 pos, uint8 pDep) {
  for (size_t i = 0; i < op.GetNumOpnds(); ++i) {
    MeExpr *replaced = TranslatePhi(*op.GetOpnd(i), phiBB, pos, pDep + 1);
    if (!replaced) {
      return nullptr;
    }
    if (replaced != op.GetOpnd(i) && replaced->IsScalar()) {
      bool isSRCand = op.GetOp() == OP_add || op.GetOp() == OP_sub || op.GetOp() == OP_cvt || op.GetOp() == OP_mul;
      auto *scalar = static_cast<ScalarMeExpr*>(replaced);
      if (isSRCand && scalar->IsDefByStmt() && scalar->GetDefStmt()->IsAssign() &&
          static_cast<AssignMeStmt*>(scalar->GetDefStmt())->isIncDecStmt) {
        return nullptr;
      }
    }
    CongruenceClass *opndVn = GetVnOfMeExpr(*replaced);
    if (!opndVn) {
      return nullptr;
    }
    op.SetOpnd(i, replaced);
  }
  auto *hashed = irmap.HashMeExpr(op);
  if (GetVnOfMeExpr(*hashed)) {
    return hashed;
  }
  (void)GetOrCreateVnAfterTrans2VnExpr(*hashed);
  return hashed;
}

MeExpr *GVN::TranslatePhiForNary(NaryMeExpr &nary, const BB &phiBB, int32 pos, uint8 pDep) {
  for (size_t i = 0; i < nary.GetNumOpnds(); ++i) {
    MeExpr *replaced = TranslatePhi(*nary.GetOpnd(i), phiBB, pos, pDep + 1);
    if (!replaced) {
      return nullptr;
    }
    CongruenceClass *opndVn = GetVnOfMeExpr(*replaced);
    if (!opndVn) {
      return nullptr;
    }
    nary.SetOpnd(i, replaced);
  }
  auto *hashed = irmap.HashMeExpr(nary);
  if (GetVnOfMeExpr(*hashed)) {
    return hashed;
  }
  (void)GetOrCreateVnAfterTrans2VnExpr(*hashed);
  return hashed;
}

MeExpr *GVN::TranslatePhiForScalar(ScalarMeExpr &scalar, const BB &phiBB, int32 pos, uint8 pDep) {
  auto found = phiBB.GetMePhiList().find(scalar.GetOstIdx());
  if (found != phiBB.GetMePhiList().end() && found->second->GetLHS() == &scalar) {
    return found->second->GetOpnd(static_cast<size_t>(static_cast<uint32>(pos)));
  }
  if (scalar.DefByBB() == &phiBB) {
    if (scalar.IsDefByStmt() && scalar.GetDefStmt()->GetRHS() != nullptr) {
      return TranslatePhi(*scalar.GetDefStmt()->GetRHS(), phiBB, pos, pDep);
    }
    return nullptr;
  }
  return &scalar;
}

MeExpr *GVN::TranslatePhi(MeExpr &expr, const BB &phiBB, int32 pos, uint8 pDep) {
  if (expr.GetDepth() + pDep > kMaxTreeSize) {
    return nullptr;
  }
  switch (expr.GetMeOp()) {
    case kMeOpIvar: {
      if (expr.IsVolatile()) {
        return nullptr;
      }
      if (static_cast<IvarMeExpr&>(expr).GetDefStmt() != nullptr) {
        return TranslatePhi(*static_cast<IvarMeExpr&>(expr).GetDefStmt()->GetRHS(), phiBB, pos, pDep);
      }
      IvarMeExpr ivar(&irmap.GetIRMapAlloc(), kInvalidExprID, static_cast<IvarMeExpr&>(expr));
      return TranslatePhiForIvar(ivar, phiBB, pos, pDep);
    }
    case kMeOpOp: {
      if (kOpcodeInfo.NotPure(expr.GetOp())) {
        return nullptr;
      }
      OpMeExpr op(static_cast<OpMeExpr&>(expr), kInvalidExprID);
      return TranslatePhiForOP(op, phiBB, pos, pDep);
    }
    case kMeOpNary: {
      auto &origin = static_cast<NaryMeExpr&>(expr);
      bool isPureIntrinsic =
          origin.GetOp() == OP_intrinsicop && IntrinDesc::intrinTable[origin.GetIntrinsic()].IsPure();
      if (origin.GetOp() != OP_array && !isPureIntrinsic) {
        return nullptr;
      }
      NaryMeExpr nary(&irmap.GetIRMapAlloc(), kInvalidExprID, static_cast<NaryMeExpr&>(expr));
      return TranslatePhiForNary(nary, phiBB, pos, pDep);
    }
    case kMeOpVar:
    case kMeOpReg: {
      if (expr.IsVolatile()) {
        return nullptr;
      }
      auto &scalar = static_cast<ScalarMeExpr&>(expr);
      return TranslatePhiForScalar(scalar, phiBB, pos, pDep);
    }
    case kMeOpAddrof:
    case kMeOpAddroffunc:
    case kMeOpAddroflabel:
    case kMeOpGcmalloc:
    case kMeOpConst:
    case kMeOpConststr:
    case kMeOpConststr16:
    case kMeOpSizeoftype:
    case kMeOpFieldsDist:
      return &expr;
    default:
      CHECK_FATAL(false, "MeOP NIY");
  }
}

bool IsConstExpr(MeExprOp op) {
  return op == kMeOpGcmalloc || op == kMeOpConst || op == kMeOpConststr || op == kMeOpConststr16 ||
         op == kMeOpSizeoftype || op == kMeOpFieldsDist;
}

void GVN::TraversalBBAntic(const BB &bb, std::vector<bool> &visited) {
  BBValueInfo *curBVI = bbValues[bb.GetID()];
  visited[bb.GetID()] = true;
  CHECK_NULL_FATAL(curBVI);
  std::set<MeExpr*> anticOut;
  bool firstSet = true;
  for (size_t i = 0; i < bb.GetSucc().size(); ++i) {
    if (!IsBBReachable(*bb.GetSucc(i)) || !visited[bb.GetSucc(i)->GetID()]) {
      continue;
    }
    auto *succ = bb.GetSucc(i);
    if (firstSet) {
      for (auto *expr : bbValues[succ->GetID()]->GetAnticSet()) {
        if (expr->GetPrimType() == PTY_agg) {
          continue;
        }
        MeExpr *translated = TranslatePhi(*expr, *succ, succ->GetPredIndex(bb), 0);
        if (!translated || IsConstExpr(translated->GetMeOp())) {
          continue;
        }
        anticOut.emplace(translated);
      }
      firstSet = false;
      continue;
    }
    auto &succAntic = bbValues[succ->GetID()]->GetAnticSet();
    for (auto it = anticOut.begin(); it != anticOut.end();) {
      auto found = std::find_if(succAntic.begin(), succAntic.end(),
          [&bb, succ, it, this] (MeExpr *cur) {
            MeExpr *translated = TranslatePhi(*cur, *succ, succ->GetPredIndex(bb), 0);
            if (!translated) {
              return false;
            }
            return GetVnOfMeExpr(**it) == GetVnOfMeExpr(*translated);
          });
      if (found == succAntic.end()) {
        it = anticOut.erase(it);
      } else {
        ++it;
      }
    }
  }
  curBVI->GetAnticSet().clear();
  curBVI->GetAnticSet().insert(anticOut.begin(), anticOut.end());
  curBVI->GetAnticSet().insert(curBVI->GetExprSet().begin(), curBVI->GetExprSet().end());
}

void GVN::RestrictPASize(MapleSet<MeExpr *, ExprDepthCmp> &pa, const std::set<MeExpr*> &paOut) const {
  const int kMaxPA = 3000;
  curGVN = this;
  auto it = paOut.begin();
  while (it != paOut.end() && pa.size() < kMaxPA) {
    pa.emplace(*it);
    ++it;
  }
  curGVN = nullptr;
}

void GVN::TraversalBBPartialAntic(const BB &bb) {
  if (bb.GetSucc().empty()) {
    return;
  }
  BBValueInfo *curBVI = bbValues[bb.GetID()];
  std::set<MeExpr*> paOut;
  for (size_t i = 0; i < bb.GetSucc().size(); ++i) {
    if (!IsBBReachable(*bb.GetSucc(i))) {
      continue;
    }
    auto &succPA = bbValues[bb.GetSucc(i)->GetID()]->GetPAnticSet();
    auto &succAntic = bbValues[bb.GetSucc(i)->GetID()]->GetAnticSet();
    for (auto *expr : succPA) {
      MeExpr *translated = TranslatePhi(*expr, *bb.GetSucc(i), bb.GetSucc(i)->GetPredIndex(bb), 0);
      if (!translated || IsConstExpr(translated->GetMeOp())) {
        continue;
      }
      paOut.emplace(translated);
    }
    if (bb.GetSucc().size() == 1) {
      continue;
    }
    for (auto *expr : succAntic) {
      if (expr->GetPrimType() == PTY_agg || expr->IsScalar()) {
        continue;
      }
      MeExpr *translated = TranslatePhi(*expr, *bb.GetSucc(i), bb.GetSucc(i)->GetPredIndex(bb), 0);
      if (!translated || IsConstExpr(translated->GetMeOp())) {
        continue;
      }
      paOut.emplace(translated);
    }
  }
  for (auto it = paOut.begin(); it != paOut.end();) {
    auto found = std::find_if(curBVI->GetAnticSet().begin(), curBVI->GetAnticSet().end(),
        [it, this] (MeExpr *expr) {
          return GetVnOfMeExpr(**it) == GetVnOfMeExpr(*expr);
        });
    if (found != curBVI->GetAnticSet().end()) {
      it = paOut.erase(it);
    } else {
      ++it;
    }
  }
  auto &pa = curBVI->GetPAnticSet();
  RestrictPASize(pa, paOut);
}

void GVN::ComputeAntic() {
  bool changed = false;
  std::vector<bool> visited(cfg.GetAllBBs().size(), false);
  do {
    changed = false;
    for (auto *node : pdom.GetReversePostOrder()) {
      auto *bb = cfg.GetBBFromID(BBId(node->GetID()));
      if (bb == cfg.GetCommonEntryBB() || bb == cfg.GetCommonExitBB() || !IsBBReachable(*bb)) {
        continue;
      }
      auto oldAntic = bbValues[bb->GetID()]->GetAnticSet();
      TraversalBBAntic(*cfg.GetBBFromID(BBId(bb->GetID())), visited);
      if (!changed && bbValues[bb->GetID()]->GetAnticSet() != oldAntic) {
        changed = true;
      }
    }
  } while (changed);
  for (auto *bb : cfg.GetAllBBs()) {
    if (!bb || bb == cfg.GetCommonEntryBB() || bb == cfg.GetCommonExitBB() || !IsBBReachable(*bb) ||
        bb->GetPred().size() <= 1) {
      continue;
    }
    CleanSet(bbValues[bb->GetID()]->GetAnticSet());
  }
  for (auto *node : pdom.GetReversePostOrder()) {
    auto *bb = cfg.GetBBFromID(BBId(node->GetID()));
    if (bb == cfg.GetCommonEntryBB() || bb == cfg.GetCommonExitBB() || !IsBBReachable(*bb)) {
      continue;
    }
    TraversalBBPartialAntic(*bb);
  }
}

bool GVN::IsPhiValue(const MeExpr &expr, const BB &phiBB) const {
  for (auto &it : phiBB.GetMePhiList()) {
    if (it.second->GetLHS()->GetMeOp() == kMeOpReg && GetVnOfMeExpr(expr) == GetVnOfMeExpr(*it.second->GetLHS())) {
      return true;
    }
  }
  return false;
}

bool GVN::IsDomValue(const MeExpr &expr, uint32 domBBID) {
  return GetVnOfMeExpr(expr) && bbValues[domBBID] &&
         bbValues[domBBID]->GetAvailSet().count(GetVnOfMeExpr(expr)->GetID()) != 0;
}

RegMeExpr *GVN::ChooseReplacePreg(const MeExpr &expr, const BB &cur) {
  if (expr.GetMeOp() != kMeOpVar) {
    return irmap.CreateRegMeExpr(expr.GetPrimType());
  }
  auto ostIdx = static_cast<const VarMeExpr&>(expr).GetOstIdx();
  auto phiFound = cur.GetMePhiList().find(ostIdx);
  if (phiFound == cur.GetMePhiList().end() || &expr != phiFound->second->GetLHS()) {
    return irmap.CreateRegMeExpr(expr.GetPrimType());
  }
  auto const found = ost2preg.find(ostIdx);
  if (found != ost2preg.end()) {
    return irmap.CreateRegMeExprVersion(*found->second);
  }
  RegMeExpr *preg = irmap.CreateRegMeExpr(expr.GetPrimType());
  (void)ost2preg.emplace(ostIdx, preg->GetOst());
  return preg;
}

AssignMeStmt *GVN::IVLikely(const MeExpr &expr, RegMeExpr &preg, RegMeExpr &predReg, const BB *cur, size_t pos) {
  if (expr.GetMeOp() != kMeOpVar) {
    return nullptr;
  }
  auto &var = static_cast<const VarMeExpr&>(expr);
  if (!var.IsDefByPhi() || var.DefByBB() != cur) {
    return nullptr;
  }
  auto *crossPhi = var.GetDefPhi().GetOpnd(pos);
  if (!crossPhi->IsDefByStmt() || !crossPhi->GetDefStmt()->GetRHS()) {
    return nullptr;
  }
  auto *defStmt = crossPhi->GetDefStmt();
  auto *defBB = crossPhi->DefByBB();
  auto *crossPhiRhs = crossPhi->GetDefStmt()->GetRHS();
  auto *replaced = irmap.ReplaceMeExprExpr(*crossPhiRhs, expr, preg, false);
  if (replaced == crossPhiRhs) {
    return nullptr;
  }
  expr2Vn[static_cast<uint32>(crossPhiRhs->GetExprID())]->AddExpr(*replaced);
  SetVnForExpr(*replaced, *expr2Vn[static_cast<uint32>(crossPhiRhs->GetExprID())]);
  AssignMeStmt *insert = irmap.CreateAssignMeStmt(predReg, *replaced, *defBB);
  defBB->InsertMeStmtAfter(defStmt, insert);
  return insert;
}

void GVN::InsertToBBPred(const MeExpr &expr, BB &cur, std::vector<std::pair<MeExpr*, bool>> &predAvail) {
  RegMeExpr *preg = ChooseReplacePreg(expr, cur);
  expr2Vn[static_cast<uint32>(expr.GetExprID())]->AddExpr(*preg);
  SetVnForExpr(*preg, *expr2Vn[static_cast<uint32>(expr.GetExprID())]);
  MePhiNode *regPhiNode = irmap.CreateMePhi(*preg);
  regPhiNode->SetDefBB(&cur);
  for (size_t i = 0; i < cur.GetPred().size(); ++i) {
    auto *predBB = cur.GetPred(i);
    auto *predExpr = predAvail[i].first;
    auto *predReg = irmap.CreateRegMeExprVersion(*preg);
    if (!predExpr) {
      // unreachable pred, fake opnd
      if (IsPrimitiveInteger(predReg->GetPrimType())) {
        predExpr = irmap.CreateIntConstMeExpr(0, predReg->GetPrimType());
      } else {
        auto *constF = GlobalTables::GetFpConstTable().GetOrCreateFloatConst(0.0);
        predExpr = irmap.CreateConstMeExpr(PTY_f32, *constF);
      }
      auto *insert = irmap.CreateAssignMeStmt(*predReg, *predExpr, *predBB);
      predBB->InsertMeStmtLastBr(insert);
      regPhiNode->GetOpnds().emplace_back(predReg);
      continue;
    }
    AssignMeStmt *insert = IVLikely(expr, *preg, *predReg, &cur, i);
    if (!insert) {
      insert = irmap.CreateAssignMeStmt(*predReg, *predExpr, *predBB);
      predBB->InsertMeStmtLastBr(insert);
    }
    expr2Vn[static_cast<uint32>(predExpr->GetExprID())]->AddExpr(*predReg);
    SetVnForExpr(*predReg, *expr2Vn[static_cast<uint32>(predExpr->GetExprID())]);
    auto *predVn = GetVnOfMeExpr(*predExpr);
    if (!predAvail[i].second && predVn) {
      (void)bbValues[predBB->GetID()]->GetAvailSet().emplace(predVn->GetID());
      (void)bbValues[predBB->GetID()]->GetInsertSet().emplace(predVn->GetID());
    }
    regPhiNode->GetOpnds().emplace_back(predReg);
  }
  cur.GetMePhiList().emplace(std::make_pair(preg->GetOstIdx(), regPhiNode));
  CongruenceClass *addedVal = expr2Vn[static_cast<uint32>(expr.GetExprID())];
  (void)bbValues[cur.GetID()]->GetAvailSet().emplace(addedVal->GetID());
  (void)bbValues[cur.GetID()]->GetInsertSet().emplace(addedVal->GetID());
}

bool ZeroInitCheck(const MeExpr &expr, const CongruenceClass &transVal) {
  if (expr.GetMeOp() != kMeOpIvar) {
    return false;
  }
  for (auto *val : transVal.GetMeExprList()) {
    if (val->GetMeOp() == kMeOpConst && static_cast<ConstMeExpr *>(val)->IsIntZero()) {
      return true;
    }
  }
  return false;
}

void GVN::InsertForPRE(BB &curBB) {
  auto *curBVI = bbValues[curBB.GetID()];
  std::vector<std::pair<MeExpr*, bool>> insertAvail(curBB.GetPred().size());  // key is pred pos
  for (auto *expr : curBVI->GetAnticSet()) {
    if (IsPhiValue(*expr, curBB)) {
      continue;  // no need more phi insertion
    }

    if (IsDomValue(*expr, dom.GetDom(curBB.GetID())->GetID())) {
      continue;  // fully redundant, no need to insert a phi
    }

    if (expr->GetOp() == OP_iaddrof) {
      auto *iaddr = static_cast<OpMeExpr*>(expr);
      if (iaddr->GetFieldID() == 0 || iaddr->GetFieldID() == 1) {
        // it's same as it's opnd but we keep it's info here, so skip it
        continue;
      }
    }

    if (expr->GetOp() == OP_cvt) {
      auto *cvt = static_cast<OpMeExpr*>(expr);
      auto fromType = cvt->GetOpndType();
      auto toType = cvt->GetPrimType();
      bool isInteger = IsPrimitiveInteger(toType) && IsPrimitiveInteger(fromType);
      bool truncToWord = isInteger &&
          GetPrimTypeSize(toType) == k4BitSize && GetPrimTypeSize(fromType) > GetPrimTypeSize(toType);
      bool expandFromWord = isInteger && GetPrimTypeSize(fromType) == k4BitSize && IsUnsignedInteger(fromType);
      if (truncToWord || expandFromWord) {
        // it costs no or cheap instruction to do this
        continue;
      }
    }

    bool allSame = true;
    bool partialSame = false;
    CongruenceClass *firstFound = nullptr;
    for (size_t i = 0; i < curBB.GetPred().size(); ++i) {
      auto *pred = curBB.GetPred(i);
      if (!IsBBReachable(*pred)) {
        insertAvail[i] = std::make_pair(nullptr, true);
        continue;
      }
      auto &predAvail = bbValues[pred->GetID()]->GetAvailSet();
      MeExpr *translated = TranslatePhi(*expr, curBB, static_cast<int32>(i), 0);
      if (!translated) {
        partialSame = false;
        allSame = false;
        break;
      }
      CongruenceClass *transVal = GetVnOfMeExpr(*translated);
      CHECK_NULL_FATAL(transVal);
      firstFound = firstFound ? firstFound : transVal;
      if (allSame) {
        allSame = transVal == firstFound;
      }
      insertAvail[i] = std::make_pair(translated, false);
      partialSame = partialSame || (predAvail.count(transVal->GetID()) != 0 && !ZeroInitCheck(*expr, *transVal));
    }

    if (!partialSame) {
      continue;
    }
    if (!allSame) {
      // NEEDFIX: dump redundant expr
      InsertToBBPred(*expr, curBB, insertAvail);
    } else if (firstFound->GetRepExpr() && !IsConstExpr(firstFound->GetRepExpr()->GetMeOp())) {
      SetVnForExpr(*expr, *firstFound);
      InsertToBBPred(*expr, curBB, insertAvail);
    }
  }
}

void GVN::InsertForFRE(BB &curBB) {
  auto *curBVI = bbValues[curBB.GetID()];
  std::vector<std::pair<MeExpr*, bool>> insertAvail(curBB.GetPred().size());  // key is pred pos
  for (auto it = curBVI->GetPAnticSet().begin(); it != curBVI->GetPAnticSet().end();) {
    auto *expr = *it;
    if (IsPhiValue(*expr, curBB)) {
      it = curBVI->GetPAnticSet().erase(it);
      continue;  // no need more phi insertion
    }

    if (IsDomValue(*expr, dom.GetDom(curBB.GetID())->GetID())) {
      it = curBVI->GetPAnticSet().erase(it);
      continue;  // fully redundant, no need to insert a phi
    }

    bool allAvail = true;
    bool transFail = false;
    for (size_t i = 0; i < curBB.GetPred().size(); ++i) {
      auto *pred = curBB.GetPred(i);
      if (!IsBBReachable(*pred)) {
        insertAvail[i] = std::make_pair(nullptr, true);
        continue;
      }
      MeExpr *translated = TranslatePhi(*expr, curBB, static_cast<int32>(i), 0);
      if (!translated) {
        allAvail = false;
        transFail = true;
        break;
      }
      auto &predAvail = bbValues[pred->GetID()]->GetAvailSet();
      CongruenceClass *transVal = GetVnOfMeExpr(*translated);
      CHECK_NULL_FATAL(transVal);
      if (predAvail.count(transVal->GetID()) == 0) {
        allAvail = false;
        break;
      }
      insertAvail[i] = std::make_pair(translated, true);
    }

    if (!allAvail) {
      transFail ? it = curBVI->GetPAnticSet().erase(it) : ++it;
      continue;
    }
    InsertToBBPred(*expr, curBB, insertAvail);
    it = curBVI->GetPAnticSet().erase(it);
  }
}

void GVN::Insert() {
  bool changed = false;
  do {
    changed = false;
    for (auto *node : dom.GetReversePostOrder()) {
      auto *curBB = cfg.GetBBFromID(BBId(node->GetID()));
      if (curBB == cfg.GetCommonEntryBB() || curBB == cfg.GetCommonExitBB() || !IsBBReachable(*curBB)) {
        continue;
      }
      auto *domBVI = bbValues[dom.GetDom(node->GetID())->GetID()];
      bool availUpdated = false;
      for (auto id : domBVI->GetInsertSet()) {
        auto &curAvail = bbValues[node->GetID()]->GetAvailSet();
        CongruenceClass *newVal = vnVector[id];
        if (curAvail.count(newVal->GetID()) != 0) {
          continue;
        }
        bbValues[node->GetID()]->GetInsertSet().emplace(id);
        bbValues[node->GetID()]->GetAvailSet().emplace(id);
        if (curBB->GetSucc().size() == 1 && curBB->GetSucc(0)->GetPred().size() > 1) {
          availUpdated = true;
        }
      }
      if (availUpdated && !changed) {
        for (auto *succ : curBB->GetSucc()) {
          if (dom.GetReversePostOrderId()[succ->GetID()] < dom.GetReversePostOrderId()[curBB->GetID()]) {
            changed = true;
            break;
          }
        }
      }
      if (curBB->GetPred().size() <= 1) {
        continue;
      }
      InsertForPRE(*curBB);
      InsertForFRE(*curBB);
    }
    if (changed) {
      for (auto *bb : cfg.GetAllBBs()) {
        if (!bb || !bbValues[bb->GetID()]) {
          continue;
        }
        bbValues[bb->GetID()]->GetInsertSet().clear();
      }
    }
  } while (changed);
}

void GVN::CodeMotion() {
  for (auto *node : dom.GetReversePostOrder()) {
    BB *bb = cfg.GetBBFromID(BBId(node->GetID()));
    if (!IsBBReachable(*bb)) {
      continue;
    }
    // DoPhiFRE may generate new stmts at begin of BB
    MeStmt *stmt = bb->GetFirstMe();
    for (auto const &phi : bb->GetMePhiList()) {
      if (phi.second->GetIsLive()) {
        DoPhiFRE(*phi.second, stmt);
      }
    }
    while (stmt) {
      MeStmt *next = stmt->GetNext();
      DoStmtFRE(*stmt);
      stmt = next;
      if (preCnt >= MeOption::gvnpreLimit) {
        return;
      }
    }
  }
}
// GVNPRE end

void GVN::Run() {
  DEBUG_LOG() << "+ Begin Generating GVN For Func <" << f.GetName() << ">\n\n";
  InitNum();
  // Tarjan/Nuutila algorithm to generate scc for cfg
  GenSCC();
  // traverse stmts and phi in RPO, and rank them from 1.
  RankStmtAndPhi();

  MarkEntryBBReachable();
  // collect useinfo
  auto &useInfo = irmap.GetExprUseInfo();
  if (useInfo.IsInvalid()) {
    useInfo.CollectUseInfoInFunc(&irmap, &dom, kUseInfoOfAllExpr);
  }
  // traverse scc in RPO
  for (auto *scc : sccTopologicalVec) {
    // scc has backedge
    if (scc->HasRecursion()) {
      GenVnForSCCIteratively(*scc);
    } else {
      GenVnForSingleBB(*scc->GetNodes().front());
    }
  }
  // GVN is fixed now
  DEBUG_LOG() << "- End Generating GVN For Func <" << f.GetName() << ">\n\n";
  gvnInsStart = static_cast<int>(f.GetMirFunc()->GetPregTab()->Size());
  if (kDebug) {
    DumpVnVector();
    DumpVnExprs();
  }
  ComputeAvail();
  ComputeAntic();
  Insert();
  CodeMotion();
  useInfo.InvalidUseInfo();
  if (!cands.empty()) {
    MeSSAUpdate ssaUpdate(f, *f.GetMeSSATab(), dom, cands);
    ssaUpdate.Run();
  }
}
// == End of GVN


// implement simple reg prop
// SimpleProp Start
class SimpleProp : public Prop {
 public:
  SimpleProp(MeFunction *meFunc, MeExprUseInfo &ui, IdentifyLoops *loops, IRMap &irMap, Dominance &dom, Dominance &pdom,
      MemPool &memPool, uint32 bbVecSize, const PropConfig &config)
  : Prop(irMap, dom, pdom, memPool, bbVecSize, config),
  func(meFunc), useInfo(ui), loopInfo(loops) {}
  ~SimpleProp() override {
    func = nullptr;
    loopInfo = nullptr;
  }

  void VisitBB(BB &bb);

 protected:
  MeExpr &PropMeExpr(MeExpr &meExpr, bool &isproped, bool atParm) override;
  void TraversalMeStmt(MeStmt &meStmt) override;
  BB *GetBB(BBId id) override {
    return func->GetCfg()->GetAllBBs()[id];
  }

 private:
  bool DealtWithSelfCopy(MeExpr &propedRHS, const ScalarMeExpr &lhs, AssignMeStmt &assign);
  bool IsSingleUse(const MeExpr &expr);

  MeFunction *func;
  uint32 cntOfPropedStmt = 0;
  MeExprUseInfo &useInfo;
  IdentifyLoops *loopInfo;
};

bool SimpleProp::IsSingleUse(const MeExpr &expr) {
  if (expr.GetMeOp() != kMeOpReg) {
    return false;
  }
  auto &regMeExpr = static_cast<const RegMeExpr&>(expr);
  if (regMeExpr.GetRegIdx() < 0) {  // special register
    return false;
  }
  if (!regMeExpr.IsDefByStmt()) {
    return false;
  }
  BB *defBB = regMeExpr.GetDefStmt()->GetBB();
  if (curBB != defBB &&
      loopInfo->GetBBLoopParent(curBB->GetBBId()) != loopInfo->GetBBLoopParent(defBB->GetBBId())) {
    return false;
  }
  auto *useSites = useInfo.GetUseSitesOfExpr(&expr);
  CHECK_NULL_FATAL(useSites);
  if (useSites->size() != 1) {
    return false;
  }
  auto useItem = useSites->front();
  return useItem.GetRef() == 1;
}

MeExpr &SimpleProp::PropMeExpr(MeExpr &meExpr, bool &isproped, bool atParm) {
  MeExprOp meOp = meExpr.GetMeOp();

  bool subProped = false;
  switch (meOp) {
    case kMeOpReg: {
      auto &regExpr = static_cast<RegMeExpr&>(meExpr);
      if (regExpr.GetRegIdx() < 0 || regExpr.GetRegIdx() < gvnInsStart) {
        return meExpr;
      }
      bool singleUse = IsSingleUse(meExpr);
      bool regCopy = regExpr.GetRegIdx() > 0 && regExpr.IsDefByStmt() && regExpr.GetDefStmt()->GetRHS() &&
          (regExpr.GetDefStmt()->GetRHS()->GetMeOp() == kMeOpReg ||
           regExpr.GetDefStmt()->GetRHS()->GetMeOp() == kMeOpConst);
      if (!singleUse && !regCopy) {
        return meExpr;
      }
      MeExpr &propMeExpr = PropReg(regExpr, atParm, false);
      if (&propMeExpr != &regExpr) {
        isproped = true;
        if (singleUse) {
          regExpr.DefByBB()->RemoveMeStmt(regExpr.GetDefStmt());
        }
      }
      return propMeExpr;
    }
    case kMeOpIvar: {
      auto *ivarMeExpr = static_cast<IvarMeExpr*>(&meExpr);
      CHECK_NULL_FATAL(ivarMeExpr);
      if (ivarMeExpr->HasMultipleMu()) {
        return meExpr;
      }
      auto *base = ivarMeExpr->GetBase();
      MeExpr *propedExpr = &PropMeExpr(utils::ToRef(base), subProped, false);
      if (propedExpr == base) {
        return meExpr;
      }
      isproped = true;
      IvarMeExpr newMeExpr(&irMap.GetIRMapAlloc(), -1, *ivarMeExpr);
      newMeExpr.SetBase(propedExpr);
      newMeExpr.SetDefStmt(nullptr);
      return utils::ToRef(irMap.HashMeExpr(newMeExpr));
    }
    case kMeOpOp: {
      auto &meOpExpr = static_cast<OpMeExpr&>(meExpr);
      OpMeExpr newMeExpr(meOpExpr, -1);
      bool needRehash = false;
      for (size_t i = 0; i < newMeExpr.GetNumOpnds(); ++i) {
        auto *opnd = meOpExpr.GetOpnd(i);
        auto &propedExpr = PropMeExpr(utils::ToRef(opnd), subProped, false);
        if (&propedExpr != opnd) {
          auto *simplified = irMap.SimplifyMeExpr(&propedExpr);
          simplified = simplified ? simplified : &propedExpr;
          newMeExpr.SetOpnd(i, simplified);
          needRehash = true;
        }
      }
      if (!needRehash) {
        return meExpr;
      }
      isproped = true;
      return utils::ToRef(irMap.HashMeExpr(newMeExpr));
    }
    case kMeOpNary: {
      auto &naryMeExpr = static_cast<NaryMeExpr&>(meExpr);
      NaryMeExpr newMeExpr(&propMapAlloc, -1, naryMeExpr);
      bool needRehash = false;
      for (size_t i = 0; i < naryMeExpr.GetOpnds().size(); ++i) {
        auto *opnd = naryMeExpr.GetOpnd(i);
        auto &propedExpr = PropMeExpr(utils::ToRef(opnd), subProped, false);
        if (&propedExpr != opnd) {
          auto *simplified = irMap.SimplifyMeExpr(&propedExpr);
          simplified = simplified ? simplified : &propedExpr;
          newMeExpr.SetOpnd(i, simplified);
          needRehash = true;
        }
      }
      if (!needRehash) {
        return meExpr;
      }
      isproped = true;
      return utils::ToRef(irMap.HashMeExpr(newMeExpr));
    }
    default:
      return meExpr;
  }
}

bool SimpleProp::DealtWithSelfCopy(MeExpr &propedRHS, const ScalarMeExpr &lhs, AssignMeStmt &assign) {
  if (propedRHS.GetMeOp() != kMeOpReg || static_cast<RegMeExpr&>(propedRHS).GetOstIdx() != lhs.GetOstIdx()) {
    return false;
  }
  // prop rhs to lhs's use
  auto *useSite = useInfo.GetUseSitesOfExpr(&lhs);
  if (!useSite) {
    return false;
  }
  for (auto &useItem : *useSite) {
    if (useItem.IsUseByStmt()) {
      auto *stmt = useItem.GetStmt();
      (void)irMap.ReplaceMeExprStmt(*stmt, lhs, propedRHS);
      useInfo.AddUseSiteOfExpr(&propedRHS, stmt);
      continue;
    }
    auto *phi = useItem.GetPhi();
    for (size_t i = 0; i < phi->GetOpnds().size(); i++) {
      if (phi->GetOpnd(i) == &lhs) {
        phi->SetOpnd(i, static_cast<RegMeExpr*>(&propedRHS));
      }
    }
    useInfo.AddUseSiteOfExpr(&propedRHS, phi);
  }
  assign.GetBB()->RemoveMeStmt(&assign);
  return true;
}

void SimpleProp::TraversalMeStmt(MeStmt &meStmt) {
  cntOfPropedStmt++;
  Opcode op = meStmt.GetOp();
  bool subProped = false;
  // prop operand
  switch (op) {
    case OP_iassign: {
      auto &ivarStmt = static_cast<IassignMeStmt&>(meStmt);
      auto *rhs = ivarStmt.GetRHS();
      auto &propedRHS = PropMeExpr(utils::ToRef(rhs), subProped, false);
      ivarStmt.SetRHS(&propedRHS);

      auto *lhs = ivarStmt.GetLHSVal();
      auto *baseOfIvar = lhs->GetBase();
      MeExpr *propedExpr = &PropMeExpr(utils::ToRef(baseOfIvar), subProped, false);
      if (propedExpr != baseOfIvar) {
        IvarMeExpr newMeExpr(&irMap.GetIRMapAlloc(), kInvalidExprID, *lhs);
        newMeExpr.SetBase(propedExpr);
        newMeExpr.SetDefStmt(nullptr);
        ivarStmt.SetLHSVal(&newMeExpr);
        ivarStmt.SetLHSVal(irMap.BuildLHSIvarFromIassMeStmt(ivarStmt));
      }
      break;
    }
    case OP_dassign:
    case OP_regassign: {
      AssignMeStmt &assignStmt = static_cast<AssignMeStmt &>(meStmt);
      auto *rhs = assignStmt.GetRHS();
      auto *lhs = assignStmt.GetLHS();
      if (rhs->GetMeOp() == kMeOpReg && lhs->GetMeOp() == kMeOpReg && rhs->GetExprID() > lhs->GetExprID() &&
          static_cast<RegMeExpr*>(rhs)->GetRegIdx() < static_cast<RegMeExpr*>(lhs)->GetRegIdx()) {
        PropUpdateDef(*assignStmt.GetLHS());
        break;
      }
      auto &propedRHS = PropMeExpr(utils::ToRef(rhs), subProped, false);
      assignStmt.SetRHS(&propedRHS);
      if (DealtWithSelfCopy(propedRHS, *lhs, assignStmt)) {
        break;
      }
      PropUpdateDef(*assignStmt.GetLHS());
      break;
    }
    case OP_asm: break;
    case OP_brtrue:
    case OP_brfalse: {
      PropConditionBranchStmt(&meStmt);
      break;
    }
    default:{
      for (size_t i = 0; i != meStmt.NumMeStmtOpnds(); ++i) {
        auto opnd = meStmt.GetOpnd(i);
        MeExpr &propedExpr = PropMeExpr(utils::ToRef(opnd), subProped, kOpcodeInfo.IsCall(op));
        meStmt.SetOpnd(i, &propedExpr);
      }
      break;
    }
  }

  // update chi
  auto *chiList = meStmt.GetChiList();
  if (chiList != nullptr) {
    switch (op) {
      case OP_syncenter:
      case OP_syncexit: {
        break;
      }
      default:
        PropUpdateChiListDef(*chiList);
        break;
    }
  }

  // update must def
  if (kOpcodeInfo.IsCallAssigned(op)) {
    MapleVector<MustDefMeNode> *mustDefList = meStmt.GetMustDefList();
    for (auto &node : utils::ToRef(mustDefList)) {
      MeExpr *meLhs = node.GetLHS();
      PropUpdateDef(utils::ToRef(static_cast<VarMeExpr*>(meLhs)));
    }
  }
}

void SimpleProp::VisitBB(BB &bb) {
  if (bbVisited[bb.GetBBId()]) {
    return;
  }
  bbVisited[bb.GetBBId()] = true;

  SetCurBB(&bb);

  bool hasDefPoint = HasDefPointInBB(bb);
  if (hasDefPoint) {
    // When traversing a new bb, create a new vector and put it into isNewVstPushedStack to record
    // whether the current bb has a new vst.
    GrowIsNewVstPushedStack();
    // update var phi nodes
    for (auto &it : std::as_const(bb.GetMePhiList())) {
      PropUpdateDef(utils::ToRef(it.second->GetLHS()));
    }
  }

  // traversal on stmt
  auto *curStmt = to_ptr(bb.GetMeStmts().begin());
  while (curStmt) {
    auto *next = curStmt->GetNext();
    TraversalMeStmt(*curStmt);
    curStmt = next;
  }

  auto &domChildren = dom.GetDomChildren(bb.GetID());
  for (auto &childbbid : std::as_const(domChildren)) {
    VisitBB(*GetBB(BBId(childbbid)));
  }
  if (hasDefPoint) {
    // If element of the top of isNewVstPushedStack is true,
    // the vstLiveStack pop one layer to recover as before when entering BB.
    RecoverVstLiveStack();
  }
}

// SimpleProp End

void MEGVN::GetAnalysisDependence(maple::AnalysisDep &aDep) const {
  aDep.AddRequired<MEDominance>();
  aDep.AddRequired<MEIRMapBuild>();
  aDep.AddRequired<MELoopAnalysis>();
  aDep.SetPreservedAll();
}

bool MEGVN::PhaseRun(maple::MeFunction &f) {
#if (defined(TARGX86_64) && TARGX86_64) || (defined(TARGX86) && TARGX86) || (defined(TARGVM) && TARGVM)
  return false;
#endif
  if (!MeOption::gvn) {
    return false;
  }
  constexpr size_t gvnSizeLimit = 3000;
  if (f.GetCfg()->GetAllBBs().size() > gvnSizeLimit) {
    // skip big func for now
    return false;
  }
  static uint32 puCnt = 0;
  if (puCnt > MeOption::gvnprePULimit) {
    return false;
  }
  puCnt++;
  f.SetGVNPreApplied(true);
  auto *domPhase = EXEC_ANALYSIS(MEDominance, f);
  Dominance *dom = domPhase->GetDomResult();
  Dominance *pdom = domPhase->GetPdomResult();
  auto *aliasClass = FORCE_GET(MEAliasClass);
  MeHDSE hdse0(f, *dom, *pdom, *f.GetIRMap(), aliasClass, DEBUGFUNC_NEWPM(f));
  hdse0.hdseKeepRef = MeOption::dseKeepRef;
  bool cfgChanged = hdse0.DoHDSESafely(&f, *GetAnalysisInfoHook());
  if (cfgChanged) {
    domPhase = FORCE_EXEC(MEDominance);
    dom = domPhase->GetDomResult();
    pdom = domPhase->GetPdomResult();
    FORCE_INVALID(MELoopAnalysis, f);
    FORCE_EXEC(MELoopAnalysis);
  }

  MapleAllocator *ma = GetPhaseAllocator();
  MemPool *tmpMP = ApplyTempMemPool();
  kDebug = DEBUGFUNC_NEWPM(f);

  MeLowerGlobals lowerGlobals(f, f.GetMeSSATab());
  lowerGlobals.Run();

  GVN gvn(*ma, *tmpMP, f, *dom, *pdom);
  gvn.Run();

  // run hdse after gvn
  MeHDSE hdse1(f, *dom, *pdom, *f.GetIRMap(), aliasClass, DEBUGFUNC_NEWPM(f));
  hdse1.hdseKeepRef = MeOption::dseKeepRef;
  cfgChanged = hdse1.DoHDSESafely(&f, *GetAnalysisInfoHook());
  if (cfgChanged) {
    domPhase = FORCE_EXEC(MEDominance);
    dom = domPhase->GetDomResult();
    pdom = domPhase->GetPdomResult();
    FORCE_INVALID(MELoopAnalysis, f);
    FORCE_EXEC(MELoopAnalysis);
  }

  // do simple prop to make ir simpler
  auto *hMap = GET_ANALYSIS(MEIRMapBuild, f);
  IdentifyLoops *identLoops = FORCE_GET(MELoopAnalysis);
  CHECK_NULL_FATAL(identLoops);
  auto propConfig = Prop::PropConfig {
      MeOption::propBase, true, MeOption::propGlobalRef, MeOption::propFinaliLoadRef, false, false, false, true
  };
  auto &useInfo = hMap->GetExprUseInfo();
  if (useInfo.IsInvalid()) {
    useInfo.CollectUseInfoInFunc(hMap, dom, kUseInfoOfScalar);
  }
  SimpleProp regProp(&f, useInfo, identLoops, *hMap, *dom,
                     *pdom, *ApplyTempMemPool(), f.GetCfg()->NumBBs(), propConfig);
  regProp.VisitBB(*f.GetCfg()->GetCommonEntryBB());
  useInfo.InvalidUseInfo();
  return false;
}
} // namespace maple
